分数: 525 点
问题陈述
给你一个三行的网格, N 列。表示单元格位于 i从顶部开始的第行和 j从左侧算起的第 列作为单元格 (i,j)。细胞 (i,j) 是一个壁细胞,如果 S_{i,j} is #,以及一个空单元格,如果是的话,还可以通过 ..
你被给予 Q 查询,您应按顺序处理。
每个查询给出整数 r 和 c,你应该翻转单元格的状态 (r,c)。也就是说,如果细胞 (r,c) 是一个壁单元,将其设为空单元,如果是空单元,则将其设为壁单元。然后,输出以下问题的答案:
考虑离开牢房 (1,1) 到单元格 (3,N) 通过重复移动到上、下、左或右相邻的空单元格。判断是否有细胞 (3,N) 是可达的,如果可达,求最小移动次数。
约束
- 2\le N\le 2\times 10^5
- S_{i,j} is
#or.. - 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 是整数。
输入
输入由标准输入按以下格式给出:
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),如果单元格
无法从单元格访问 (3,N) 无法从单元格访问 (1,1) 在 i第次查询,打印 -1;如果可达,则打印最小步数。
示例输入 1
5 .#... .#.#. ...#. 3 1 2 1 2 2 3
示例输出 1
6 10 -1
在第一个查询中,翻转单元格的状态 (1,2)。结果,每个细胞的状态变为:
..... .#.#. ...#.
此时,通过从单元格移动 (1,1) 通过细胞 (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) 按顺序,您可以到达单元格 (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) 按顺序,您可以到达单元格 (3,5) 十步。
在第三个查询中,翻转cell的状态 (2,3)。结果,每个细胞的状态变为:
.#... .###. ...#.
此时,无论你如何移动,都无法到达cell (3,5) 来自单元格 (1,1).
示例输入 2
7 .#..... .#..#.. ...#... 6 2 5 3 4 3 5 2 5 1 4 1 4
示例输出 2
10 8 10 12 -1 12