Shortest Path Query

AtCoder

IDabc429_f

Time4000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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

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)$.

Input #2

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Shortest Path Query",
    "description": {
      "content": "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 `#`,",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc429_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 `#`,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments