文理学院程序设计在线练习


迷宫问题(计算几种走法)

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 234   Accepted Submission(s): 133
Problem Description

一天,小明不小心进入了一个迷宫,现在请你帮助他判断能否出走出迷宫,如果可能,则输出一共有多少种不同的走法(对于某种特定的走法,必须保证不能多次走到同一个位置). 如果不能走到出口,则输出impossible. 每次走只能是上下左右4个方向.


Input

每次首先2个数n,m(0<n,m<=100),代表迷宫的高和宽,然后n行,每行m个字符,
'S'代表你现在所在的位置,
'T'代表迷宫的出口,
'#'代表墙,你是不能走的,
'.'代表路,可以走.

Output

输出一共有多少种不同的走法,不能走出输出impossible.

Sample Input
4 4
S...
#..#
..#.
...T
4 4
S...
#..#
..#.
..#T  
Sample Output
4
impossible