迷宫最短路径
题号：NC235947
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个大小为  的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个的通道移动，但不能走出迷宫。字符'#'表示墙壁，'.'表示空地，'S'表示你的起始位置，'T'表示终点。你需要求出从起点到终点的最短路径数，由于路径数可能很多，你只需要输出最短路径的个数   的结果。

输入描述:

第一行输入两个整数 
接下来 N 行，每行 M 个字符，描述迷宫的地图。字符仅由'.','#','S'和'T'组成，保证包含且仅包含一个字符'S'和一个字符'T'。

输出描述:

输出一行一个整数，表示从起点到终点的最短路径数 
示例1

输入

复制 
3 4
S##.
...#
...T

输出

复制 
3
示例2

输入

复制 
10 10
..........
..........
.....#....
.....#....
...S.#....
.#####....
..........
.....#.#.#
.....#....
.....#.#.T

输出

复制 
180