← 返回比赛

已结束 GESP排位赛 #2

← 上一题下一题 →

A1522 | $能量场$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在一个遥远的星球上，存在一个神秘的能量场。这个能量场是一个 $N \times M$ 的矩形，每一个单元都是一个能量单元。勇敢的探险家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$。

输出格式

输出一个整数，表示从起始能量单元 $A$ 恰好在 $T$ 步到达目标能量单元 $B$ 的不同路径输出一个整数，表示从起始能量单元 $A$ 恰好在 $T$ 步到达目标能量单元 $B$ 的不同路径数。 答案可能非常大，需要对 $998244353$ 取模再输出。

输入输出样例

输入 #1

4 5 6
...*.
...*.
.....
.....
1 3 1 5

输出 #1

输入 #2

4 5 8
...*.
...*.
.....
.....
1 3 1 5

输出 #2

C++ 编辑器

输入

输出