给定一个$N \times M$的网格，每个单元格可能是障碍物1或空单元格0。铅笔会从所有方向攻击你。铅笔在遇到障碍物时会停止。你每单位时间可以移动到相邻的四个方向（上下左右）的单元格。你需要处理$Q$个查询，每个查询给出铅笔的攻击方向和你当前的位置，找到到达安全单元格的最小时间，或者判断是否不可能。
picture source: https://www.twoplayergames.org/
输入
第一行包含两个整数$N$和$M$。
接下来$N$行，每行包含一个长度为$M$的字符串，由0和1组成，表示网格。其中0表示空单元格，1表示障碍物。
接下来一行包含一个整数$Q$。
接下来$Q$行，每行包含一个字符$D$和两个整数$x$, $y$，表示铅笔的攻击方向和你当前的位置。
输出
对于每个查询，输出到达安全单元格的最小时间，如果不可能则输出-1。
数据范围
对于所有测试数据，保证：
$1 \le N,M$ 和 $N \times M \le 9 \times 10^6$
$1 \le Q \le 5 \times 10^5$
$1 \le x \le N$
$1 \le y \le M$
$D =$ L / R / U / D
| 数据编号 | $N, M$ | $Q$ | 特殊性质 |
|---|---|---|---|
| 1 | $N=1, M \le 100$ | $\le 100$ | 无 |
| 2-5 | $N=2, M=2$ | $\le 100$ | 无 |
| 6-8 | $N=2, M \le 10^6$ | $\le 100$ | 所有障碍物都在第一行 |
| 9-10 | $N=2, M \le 10^6$ | $\le 5 \times 10^5$ | 所有障碍物都在第一行 |
| 11-15 | $N \times M \le 9 \times 10^6$ | $\le 5$ | 铅笔总是向下移动 |
| 16-20 | $N \times M \le 9 \times 10^6$ | $\le 5 \times 10^5$ | 无 |
Sample Test Cases
| Input | Output | |
|---|---|---|
| 3 3 000 010 010 3 R 1 2 U 3 1 D 3 3 |
2 3 -1 |
|
对于第一个查询，最短路径为(1,2)->(1,3)->(2,3)。 对于第二个查询，最短路径为(3,1)->(2,1)->(1,1)->(1,2)。 对于第三个查询，不可能不受到攻击。 |
||
| 7 7 0100001 0000010 0000000 0001010 1010000 0000000 0000110 8 D 7 2 R 3 2 L 3 2 L 6 3 U 2 7 D 6 6 L 6 2 R 6 7 |
0 2 1 1 2 0 1 1 |
|
对于第一个查询，起始位置是安全的。 对于第二个查询，最短路径为(3,2)->(4,2)->(5,2)。 对于第五个查询，最短路径为(2,7)->(3,7)->(3,6)。 |
||
| /pencil3.in | /pencil3.ans | |
此样例满足第2-5测试点的限制 |
||
| /pencil4.in | /pencil4.ans | |
此样例满足第6-8测试点的限制 |
||
| /pencil5.in | /pencil5.ans | |
此样例满足第9-10测试点的限制 |
||
| /pencil6.in | /pencil6.ans | |
此样例满足第11-15测试点的限制 |
||
| /pencil7.in | /pencil7.ans | |
此样例满足第16-20测试点的限制 |
||
Scoring: Per Case
Authored by s22l19, s23f32 and wy24215
Appeared in 2025 Mini Comp 4 [WY Interschool Pre-SDIC]