问题 D: 小A的通勤系列二

问题 D: 小A的通勤系列二

时间限制: 1 Sec  内存限制: 128 MB
提交: 157  解决: 45
[状态] [讨论版] [提交] [命题人:]
题目描述
小A下了地铁需要经过一个公园才到公司,小A经过的公园是一个长N宽M的矩形,小A每天从左下角进入公园,从右上角走出公园。这天小A下地铁比较早,想计算一下从进入公园到走出公园一共有多少种方式?为了不浪费时间,小A总是向上或者向右移动。
小A经过查阅,公园内只有可行走的道路和不可行走的花园。小A将公园地图记录下来,使用符号代替,S代表起点,E代表终点,.代表道路,#代表花园。
输入
第一行输入两个整数N,M分别代表公园的长和宽 2<=N,M<=1000
接下来输入N行,每行输入M个字符,代表公园的地图。
输出
输出一个整数,代表小A有多少种方式走出公园。结果对998244353取模。
样例输入 Copy
3 4
...E
.#..
S...
样例输出 Copy
4