Overview

This problem asks you to find the shortest path from S to G on an unweighted grid.
Since you can move one cell at a time in four directions (up, down, left, right), you can efficiently find the minimum number of cells traversed using Breadth-First Search (BFS).

Analysis

The key point is that the cost of each move is the same (1 step).
For such “all edge weights are equal” shortest path problems, BFS is optimal.

If you naively try “all possible paths” using DFS (Depth-First Search), the number of paths explodes in mazes with many branches, making it far too slow for \(N \le 500\).
Additionally, with DFS, the first path found is not necessarily the shortest, so guaranteeing the shortest path would require an enormous amount of exploration.

On the other hand, BFS explores in order of distance 1, distance 2, distance 3… from the start.
Therefore, the distance at the moment a cell is reached for the first time is the shortest distance.
Using this property, the value at the moment we reach G is the answer.

In this problem, we need to output the “number of cells on the path (including S and G)” rather than the “number of moves.”
So in the implementation, we start with dist[S] = 1 and increment by +1 for each adjacent cell, directly tracking the “number of cells traversed.”

Algorithm

1. Read the input and find the coordinates of S and G in the grid.
   
2. Prepare a dist array (unvisited cells are -1).
   
3. Perform BFS using a deque as the queue.
   
   • Initial state: enqueue S and set dist[S] = 1
     
4. Dequeue (x, y) and check all 4 directions (up, down, left, right).
   For each cell (nx, ny) that satisfies:
   • It is within the grid
     
   • It is not a wall #
     
   • It has not been visited yet (dist == -1)
     

Set dist[nx][ny] = dist[x][y] + 1 and enqueue it.
5. If the dequeued cell is G, output its dist and terminate.
(Since this is BFS, this value is guaranteed to be the minimum.)

Complexity

• Time complexity: \(O(N^2)\)
  Each cell is enqueued at most once, and for each cell we check at most 4 directions.
• Space complexity: \(O(N^2)\)
  The dist array and queue may hold up to \(N^2\) cells.

Implementation Notes

• Since the answer to this problem is the “number of cells traversed” rather than the “number of moves,” it is important to set dist[S]=1.
  If you set dist[S]=0, you would need to add +1 as a correction at the end.

• Visit management can be unified using dist[nx][ny] == -1, keeping it simple (no need for a separate visited array).

• For \(N=500\), the input is large, so using sys.stdin.readline ensures stable and fast reading.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    grid = [input().strip() for _ in range(N)]

    sx = sy = gx = gy = -1
    for i in range(N):
        row = grid[i]
        for j, ch in enumerate(row):
            if ch == 'S':
                sx, sy = i, j
            elif ch == 'G':
                gx, gy = i, j

    dist = [[-1] * N for _ in range(N)]
    q = deque()
    q.append((sx, sy))
    dist[sx][sy] = 1  # マス数として数えるため開始を1にする

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        x, y = q.popleft()
        if x == gx and y == gy:
            print(dist[x][y])
            return
        nd = dist[x][y] + 1
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and dist[nx][ny] == -1 and grid[nx][ny] != '#':
                dist[nx][ny] = nd
                q.append((nx, ny))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.