Overview

This problem asks us to minimize the “number of times we enter a P cell” when moving from S to G.
Since each move costs either 0 (entering S, G, or O) or 1 (entering P), we can efficiently compute the minimum damage using 0-1 BFS.

Analysis

The two key observations are:

1. What we want to minimize is not the “number of steps” but the “number of times we enter P”
   In other words, among paths of the same length, the one with fewer P visits is better.

2. The damage increase per move is either 0 or 1

   • If the destination is P → cost 1
   • Otherwise (S, G, O) → cost 0
   • B cells are impassable in the first place

This shortest path problem with “edge costs of 0 or 1” can also be solved with Dijkstra’s algorithm, but since the number of vertices can be as large as \(10^6\), the lighter 0-1 BFS is more effective.
A naive standard BFS (minimizing step count) would not minimize damage, resulting in WA.

Also, since “the same cell can be visited any number of times,” the state only needs to be the “cell position,” and it suffices to store the minimum damage to reach each cell in dist[v].

Algorithm

1. Read the grid and manage the positions of S and G as 1D indices (r*W+c).
2. Initialize the dist array with INF, and set dist[S]=0.
3. Perform 0-1 BFS using a deque.
   • From the current cell v, check the four adjacent directions (up, down, left, right)
   • Ignore walls B
   • If the destination is P, set weight w=1; otherwise, w=0
   • If nd = dist[v] + w improves the current distance, update it
     • When w=0, use appendleft (front of deque)
     • When w=1, use append (back of deque)
4. When G is popped from the deque, its dist[G] is guaranteed to be minimal, so output it immediately and terminate.
5. If G is never reached, output -1.

In 0-1 BFS, by processing cost-0 transitions first, the deque achieves an ordering equivalent to Dijkstra’s priority queue.

Complexity

• Time complexity: \(O(HW)\)
  (Each cell undergoes at most a constant number of relaxation operations)
• Space complexity: \(O(HW)\)
  (dist array and deque)

Implementation Notes

• Since \(H \times W\) can be large, use input = sys.stdin.readline for fast input.

• Converting coordinates to 1D (v = r*W+c) allows managing dist as a single array, which is faster.

• Note that the weight is determined by whether the destination cell is P (not the current cell).

• By checking v == g at pop time and returning immediately, we can skip unnecessary exploration.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip() for _ in range(H)]

    s = g = -1
    for i in range(H):
        row = A[i]
        for j, ch in enumerate(row):
            if ch == 'S':
                s = i * W + j
            elif ch == 'G':
                g = i * W + j

    INF = 10**18
    N = H * W
    dist = [INF] * N
    dist[s] = 0
    dq = deque([s])

    while dq:
        v = dq.popleft()
        if v == g:
            print(dist[v])
            return

        r, c = divmod(v, W)
        base = dist[v]

        # up
        if r > 0:
            nv = v - W
            ch = A[r - 1][c]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # down
        if r + 1 < H:
            nv = v + W
            ch = A[r + 1][c]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # left
        if c > 0:
            nv = v - 1
            ch = A[r][c - 1]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # right
        if c + 1 < W:
            nv = v + 1
            ch = A[r][c + 1]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.