F - Shortest Path Query Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

3 行 N 列のグリッドが与えられます。上から i 行目、左から j 列目のマスをマス (i,j) と表します。マス (i,j) には S_{i,j} が # ならば壁マスで、 . ならば空きマスであり通行可能です。

Q 個のクエリが与えられるので、順に処理してください。

各クエリでは整数 r,c が与えられるので、マス (r,c) の状態を反転させてください。つまり、マス (r,c) が壁マスならば空きマスにし、空きマスならば壁マスにしてください。その後、以下の問題の答えを出力してください。

マス (1,1) から上下左右に隣接する空きマスに移動する操作を繰り返してマス (3,N) に移動することを考えます。このとき、マス (3,N) に到達できるか判定し、到達できる場合は操作回数の最小値を求めてください。

制約

  • 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 は整数

入力

入力は以下の形式で標準入力から与えられる。

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) には、 i 番目のクエリにおいてマス (1,1) からマス (3,N) に到達不可能ならば -1 を、到達可能ならば操作回数の最小値を出力せよ。

入力例 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

出力例 1

6
10
-1

1 つ目のクエリではマス (1,2) の状態を反転させます。その結果、各マスの状態は以下のようになります。

.....
.#.#.
...#.

このとき、マス (1,1) から順にマス (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) と移動することで 6 回の操作でマス (3,5) に到達することができます。

2 つ目のクエリではマス (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) に到達することができます。

3 つ目のクエリではマス (2,3) の状態を反転させます。その結果、各マスの状態は以下のようになります。

.#...
.###.
...#.

このとき、どのように操作してもマス (1,1) からマス (3,5) に到達することはできません。

入力例 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

出力例 2

10
8
10
12
-1
12

Score : 525 points

Problem Statement

You are given a grid with three rows and N columns. Denote the cell at the i-th row from the top and j-th column from the left as cell (i,j). Cell (i,j) is a wall cell if S_{i,j} is #, and an empty cell and passable if it is ..

You are given Q queries, which you should process in order.

Each query gives integers r and c, and you should flip the state of cell (r,c). That is, if cell (r,c) is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem:

Consider moving from cell (1,1) to cell (3,N) by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell (3,N) is reachable, and if reachable, find the minimum number of moves.

Constraints

  • 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 are integers.

Input

The input is given from Standard Input in the following format:

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

Each query is given in the following format:

r c

Output

Print Q lines.

On the i-th line (1\le i\le Q), if cell (3,N) is unreachable from cell (1,1) in the i-th query, print -1; if reachable, print the minimum number of moves.

Sample Input 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

Sample Output 1

6
10
-1

In the first query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.....
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in six moves.

In the second query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.#...
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in ten moves.

In the third query, flip the state of cell (2,3). As a result, the state of each cell becomes:

.#...
.###.
...#.

At this time, no matter how you move, you cannot reach cell (3,5) from cell (1,1).

Sample Input 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

Sample Output 2

10
8
10
12
-1
12