Overview

If we consider each cell as a vertex and up/down/left/right movements as edges, this problem becomes finding the “minimum cost path from S to G.”
Since the cost is \(1\) only when moving to P and \(0\) otherwise, we can solve it efficiently using 0-1 BFS.

Analysis

What we want to minimize in this problem is not the “number of moves” but the number of times we enter P.

For example, if there are:

• A path of 5 steps that steps on P 2 times
• A path of 8 steps that steps on P 0 times

the answer is the latter.
Therefore, simply finding the “shortest number of steps” as in a regular BFS will not give the correct answer.

---

For each move, we define the cost as follows:

• Moving to P: cost \(1\)
• Moving to S, G, O: cost \(0\)
• Cannot move to B

Then the problem can be rephrased as:

Find the shortest distance from start S to goal G in a graph where all edge weights are either \(0\) or \(1\).

---

Why 0-1 BFS instead of Dijkstra?

Of course, Dijkstra’s algorithm can also solve this.
However, since edge weights in this problem are only of two types, \(0\) and \(1\), using 0-1 BFS leads to a lighter implementation with a time complexity of \(O(V+E)\).

The constraint is \(H \times W \leq 10^6\), which is quite large, so in Python, 0-1 BFS is safer than Dijkstra with \(O(E \log V)\).

---

How 0-1 BFS works

Regular BFS uses a queue, but 0-1 BFS uses a deque (double-ended queue).

When moving from the current position to an adjacent cell:

• For a cost \(0\) move: use appendleft
• For a cost \(1\) move: use append

This ensures that the order of extraction from the deque is maintained in “non-decreasing order of distance,” allowing us to find shortest distances just like Dijkstra’s algorithm.

---

Example

For instance, when moving from a cell to an adjacent cell:

• Moving to O → no damage increase → cost \(0\)
• Moving to P → damage increases by \(1\) → cost \(1\)

So candidates moving to O or G are inserted at the front of the deque, and candidates moving to P are inserted at the back.

This ensures that “paths with less damage” are explored with priority.

Algorithm

1. Store the maze as a 1-dimensional array.
2. Create a sentinel-padded array by filling the entire border with B.
   • This eliminates the need to write boundary checks for each up/down/left/right movement.
3. Let dist[v] be the “minimum damage to reach cell v from S.”
4. Set dist[start] = 0 and perform 0-1 BFS.
5. From the current position v, examine each adjacent cell nv in the four directions.
   • If B, skip
   • Otherwise: $\( nd = dist[v] + \begin{cases} 1 & (\text{destination is } P) \\ 0 & (\text{otherwise}) \end{cases} \)$
6. If nd < dist[nv], update it.
   • If P, add to the back of the deque
   • Otherwise, add to the front of the deque
7. When G is extracted from the deque, its distance is the minimum, so output the answer.
8. If G is never reached, output -1.

---

Why this is correct

The cost of each move is determined by “whether the destination is P” and is always \(0\) or \(1\).
Therefore, this problem is a shortest path problem to which 0-1 BFS can be directly applied.

Furthermore, in 0-1 BFS, when a vertex is extracted from the deque, its minimum distance is finalized at that point.
Thus, dist[G] at the moment G is extracted is the desired minimum cumulative damage.

Complexity

• Time complexity: \(O(HW)\)
• Space complexity: \(O(HW)\)

※ Treating each cell as a vertex, the number of vertices is \(O(HW)\), and each vertex has at most 4 edges, so the number of edges is also \(O(HW)\).
Since 0-1 BFS runs in \(O(V+E)\), the overall complexity is \(O(HW)\).

Implementation Details

• A sentinel-padded array is used, filling the entire border of the maze with B.
  This eliminates the need for boundary checks like 0 <= ni < H every time.

• Instead of a 2-dimensional array, a 1-dimensional array is used, where adjacent cells are represented as:

  • Left: -1
  • Right: +1
  • Up: -PW
  • Down: +PW

• To speed up character comparisons, the board is stored as a bytearray, and B, P, etc. are compared using their character codes.

• In 0-1 BFS, the same vertex may be added to the deque multiple times, so a done array is used to track “whether a vertex is finalized.” This reduces unnecessary processing.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline

    H, W = map(int, input().split())
    PW = W + 2
    PH = H + 2
    N = PW * PH

    B = ord('B')
    P = ord('P')

    grid = bytearray([B]) * N
    start = -1
    goal = -1

    for i in range(H):
        row = input().strip()
        base = (i + 1) * PW + 1
        grid[base:base + W] = row

        j = row.find(b'S')
        if j != -1:
            start = base + j

        j = row.find(b'G')
        if j != -1:
            goal = base + j

    INF = 10**18
    dist = [INF] * N
    done = bytearray(N)

    dq = deque([start])
    dist[start] = 0

    offsets = (-1, 1, -PW, PW)

    while dq:
        v = dq.popleft()
        if done[v]:
            continue
        done[v] = 1

        if v == goal:
            print(dist[v])
            return

        dv = dist[v]
        for off in offsets:
            nv = v + off
            ch = grid[nv]
            if ch == B:
                continue

            nd = dv + (ch == P)
            if nd < dist[nv]:
                dist[nv] = nd
                if ch == P:
                    dq.append(nv)
                else:
                    dq.appendleft(nv)

    print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.