编程题
### 问题描述 桥桥是一个冒险家,他喜欢探索未知的领域。有一天,他来到一个巨大的丛林,丛林是由 $n \times m$ 个格子组成,每个格子要么是安全的,要么是一个危险的炸弹。 桥桥的任务是从 $(1,1)$ 出发,走到 $(n,m)$,然后再返回到起点 $(1,1)$。但是,他必须遵守一些规则,以确保不受伤害。在桥桥第一次到达 $(n,m)$ 之前,他只能向下或者向右走,也就是说只能从 $(n,m)$ 到达 $(n+1,m)$ 或者 $(n,m+1)$, 不允许向左或向上。一旦桥桥到达了 $(n,m)$,他只能向上或者向左走,也就是说只能从 $(n,m)$ 到达 $(n-1,m)$ 或者 $(n,m-1)$,不允许向下或向右。 桥桥非常谨慎,他不想走到炸弹上,因此他希望知道在不受伤害的情况下,有多少种不同的走法可以从 $(1,1)$ 走到 $(n,m)$ 然后再返回到 $(1,1)$。由于数量可能很大,请输出对 $998244353$ 取模的结果。 ### 输入格式 第一行输入两个整数 $n$ 和 $m$ ,表示迷宫的行数和列数。 接下来输入 $n$ 行,每行包含 $m$ 个字符,其中每个字符可以是 `S`(安全的格子)或 `B`(炸弹格子)。 ### 输出格式 输出一个整数,表示在不受伤害的情况下,从 $(1,1)$ 走到 $(n,m)$ 然后返回到 $(1,1)$ 的不同走法数量。由于数量可能很大,请输出对 $998244353$ 取模的结果。 ### 样例输入 ``` 3 3 SBB SSS SSS ``` ### 样例输出 ``` 9 ``` ### 说明 并不保证 $(1,1)$ 和 $(n,m)$ 一定是 `S` 方块。 ### 评测数据范围 $1 \le n,m \le 1000$。
查看答案
赣ICP备20007335号-2