AT_abc429_f [ABC429F] Shortest Path Query
题目描述
给你一个包含三行 $N$ 列的网格。我们用从上到下的第 $i$ 行、从左到右的第 $j$ 列的单元格记作 $(i,j)$。若 $S_{i,j}$ 为 `#`，则 $(i,j)$ 是墙格，否则为 `.` 时，$(i,j)$ 是空格且可通过。
现在有 $Q$ 个查询，请按顺序依次处理。
每个查询给出整数 $r$ 和 $c$，你需要将 $(r,c)$ 这一格的状态反转。如果该格原本是墙格，请改为空格，原本是空格则改为墙格。然后，输出以下问题的答案：
> 设你从 $(1,1)$ 出发，每次只能走到相邻的上、下、左、右的空格，能否到达 $(3,N)$？如果能到达，请输出最少需要多少步。
输入格式
输入从标准输入读入，格式如下：
> $N$
> $S_{1,1}S_{1,2}\ldots S_{1,N}$
> $S_{2,1}S_{2,2}\ldots S_{2,N}$
> $S_{3,1}S_{3,2}\ldots S_{3,N}$
> $Q$
> $\text{query}_1$
> $\text{query}_2$
> $\vdots$
> $\text{query}_Q$
每个查询的格式为：
> $r\ c$
输出格式
请输出 $Q$ 行。
对于第 $i$ 次查询（$1\le i\le Q$），若此时 $(1,1)$ 无法到达 $(3,N)$，请输出 `-1`，否则输出最少所需的步数。
说明/提示
### 样例解释 1
第一次查询，将 $(1,2)$ 的状态反转。此时网格变为：
```
.....
.#.#.
...#.
```
此时，可以依次经过 $(1,1)$、$(1,2)$、$(1,3)$、$(1,4)$、$(1,5)$、$(2,5)$、$(3,5)$，共需 6 步到达 $(3,5)$。
第二次查询，再次将 $(1,2)$ 状态反转。此时网格变为：
```
.#...
.#.#.
...#.
```
此时，可以依次经过 $(1,1)$、$(2,1)$、$(3,1)$、$(3,2)$、$(3,3)$、$(2,3)$、$(1,3)$、$(1,4)$、$(1,5)$、$(2,5)$、$(3,5)$，共需 10 步到达 $(3,5)$。
第三次查询，将 $(2,3)$ 状态反转。此时网格变为：
```
.#...
.###.
...#.
```
此时，无论如何移动，都无法从 $(1,1)$ 到达 $(3,5)$。
### 数据范围
- $2\le N\le 2\times 10^5$
- $S_{i,j}$ 只可能是 `#` 或 `.`。
- $S_{1,1}=S_{3,N}=.$
- $1\le Q\le 2\times 10^5$
- $1\le r\le 3$
- $1\le c\le N$
- $(r,c)\neq (1,1),\ (3,N)$
- $N, Q, r, c$ 均为整数。
由 ChatGPT 5 翻译