A1524. 能量场
编程题
普及/提高-
知识点
题目描述
在一个遥远的星球上，存在一个神秘的能量场。这个能量场是一个 $N \times M$ 的矩形，每一个单元都是一个能量单元。勇敢的探险家AC狗获得了一种特殊的装置，可以在这个能量场中移动。但这个装置有一个特点，只能在任意一步向相邻的四个能量单元移动（上、下、左、右）。
AC狗从一个能量单元 $A$ $(R_1, C_1)$ 开始，他的目的是要在恰好 $T$ 步内到达另一个指定的能量单元 $B$ $(R_2, C_2)$。你能帮助他计算出有多少种不同的路径可以达到目标吗？其中不同的路径判断条件为 $T$ 步中至少存在一次移动的方向不同。
PS：在能量场中，. 表示该能量单元是安全的，而 * 表示该能量单元存在危险，AC狗不能进入。AC狗在移动的过程中，必须确保不会进入危险的能量单元，并且他的移动范围不能超出能量场的边界。
AC狗从一个能量单元 $A$ $(R_1, C_1)$ 开始，他的目的是要在恰好 $T$ 步内到达另一个指定的能量单元 $B$ $(R_2, C_2)$。你能帮助他计算出有多少种不同的路径可以达到目标吗？其中不同的路径判断条件为 $T$ 步中至少存在一次移动的方向不同。
PS：在能量场中，. 表示该能量单元是安全的，而 * 表示该能量单元存在危险，AC狗不能进入。AC狗在移动的过程中，必须确保不会进入危险的能量单元，并且他的移动范围不能超出能量场的边界。
输入格式
第一行包含三个正整数 $N$、$M$、$T$，表示能量场的行数和列数，以及需要在恰好 $T$ 步到达目标能量单元。
接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，描述该行的能量场状态。其中. 表示安全的能量单元，* 表示危险的能量单元。
最后一行 $4$ 个整数 $R_1,C_1,R_2,C_2$。
接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，描述该行的能量场状态。其中. 表示安全的能量单元，* 表示危险的能量单元。
最后一行 $4$ 个整数 $R_1,C_1,R_2,C_2$。
输出格式
输出一个整数，表示从起始能量单元 $A$ 恰好在 $T$ 步到达目标能量单元 $B$ 的不同路径数。
答案可能非常大，需要对 $998244353$ 取模再输出。
答案可能非常大，需要对 $998244353$ 取模再输出。
输入输出样例
输入 #1
4 5 6 ...*. ...*. ..... ..... 1 3 1 5
输出 #1
1
输入 #2
4 5 8 ...*. ...*. ..... ..... 1 3 1 5
输出 #2
18
说明/提示
在 $6$ 步内从 $(1,3)$ 走到 $(1,5)$ 的方法只有一种。
但是 $8$ 步之内有许许多多的路径：
$(1,3) -> (1,2) -> (1,3) -> ... -> (1,5)$
$(1,3) -> (2,3) -> (1,3) -> ... -> (1,5)$
$(1,3) -> (2,3) -> (3,3) -> (2,3) ... -> (1,5)$
...总共有18种路径
**【数据范围】**
对于 $20\%$ 的数据，$1\leq N,M \leq 10, 1 \le t \le 20$
对于 $50\%$ 的数据，$1\leq N,M \leq 20, 1 \le t \le 50$
对于 $100\%$ 的数据，$1\leq N,M \leq 100, 1 \le t \le 200$
但是 $8$ 步之内有许许多多的路径：
$(1,3) -> (1,2) -> (1,3) -> ... -> (1,5)$
$(1,3) -> (2,3) -> (1,3) -> ... -> (1,5)$
$(1,3) -> (2,3) -> (3,3) -> (2,3) ... -> (1,5)$
...总共有18种路径
**【数据范围】**
对于 $20\%$ 的数据，$1\leq N,M \leq 10, 1 \le t \le 20$
对于 $50\%$ 的数据，$1\leq N,M \leq 20, 1 \le t \le 50$
对于 $100\%$ 的数据，$1\leq N,M \leq 100, 1 \le t \le 200$