← 返回题目列表

AtCoder · abc429_f

I. 最短路径查询

中文机器翻译题面 查看原题

分数: 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