Problem1863--简单迷宫题

1863: 简单迷宫题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

众多单机小游戏中都有王子救公主的情节,小波也脑补了一个迷宫游戏。现有一大小为n*m二维迷宫,告诉你王子和公主的位置,小波觉得没有点实力是不配当王子的,于是王子每次可以向他的八个方向走一步(即:上、下、左、右、左上、左下、右上、右下)。迷宫中存在一些墙壁(用'#'表示),同时还存在一些陷阱(用'*'表示,在这个游戏中,保证王子能够快速的发现陷阱并绕开,具体见样例),正常可以行走的路用'.'表示,王子的位置用'S'表示,公主的位置用'E'表示。现问你王子有多少条路可以营救公主(当然王子足够聪明,不会回头路)。

Input

第一行,迷宫的大小n、m(n,m<=100)。

接下来输入整个地图。

Output

一行,表示王子有多少种路线可以营救公主。

Sample Input Copy

3 3
*.S
*..
*E#

Sample Output Copy

10

Source/Category