Overview

This is a problem where, given an \(N \times N\) maze, you need to find the minimum number of cells visited when moving up, down, left, or right from the start S to the goal G.

Since the cost of each move is \(1\), the shortest path can be found using Breadth-First Search (BFS).

Analysis

In this problem, if we consider each cell as a vertex and edges between adjacent passable cells, the grid can be viewed as a graph.

Movement is only possible to adjacent cells in the four cardinal directions (up, down, left, right), and each move counts as one step. In other words, this becomes a problem of finding the shortest distance in a graph where all edge weights are equal.

In such cases, Breadth-First Search (BFS) is suitable.

For example, if we explore cells in order of increasing distance from the start, the distance at which we first reach a cell is the shortest distance to that cell.

On the other hand, if we proceed with a naive DFS, the first path found is not necessarily the shortest. Additionally, if we try to enumerate all paths, the number of paths becomes extremely large, making it infeasible for \(N \leq 500\).

Therefore, we efficiently find the shortest path using BFS, which visits each cell at most once.

Also, what this problem asks for is not the “number of moves” but the “number of cells visited.”
For this reason, if we set the distance of the starting cell to \(1\) instead of \(0\), we can directly output the value upon reaching the goal as the answer.

Algorithm

We perform BFS with the following steps:

1. Read the grid
2. Find the positions of S and G
3. Prepare an array dist to manage the shortest distance to each cell
   • Unvisited cells are -1
   • The starting cell is 1
4. Enqueue the starting cell
5. Repeat the following until the queue is empty:
   • Dequeue the current position from the front of the queue
   • If the current position is the goal, output its distance and terminate
   • Check the adjacent cells in all four directions (up, down, left, right)
   • If the adjacent cell is within the grid, is not a wall #, and has not been visited yet, update the distance and enqueue it

Since BFS explores cells in order of increasing distance, the first time we reach the goal, it is guaranteed to be the shortest path.

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N^2)\)

Each cell is enqueued at most once, and for each cell we check at most \(4\) directions (up, down, left, right), so the time complexity is \(O(N^2)\).

The distance array dist and the queue hold at most \(N^2\) cells, so the space complexity is also \(O(N^2)\).

Implementation Notes

• In Python, use collections.deque for the BFS queue.

  • Avoid list.pop(0) as it takes \(O(N)\).

• Grid indices are handled as \(0\)-indexed in the code.

• By setting dist[sx][sy] = 1, we can directly manage the “number of cells visited.”

• The conditions for moving to an adjacent cell are as follows:

  • It is within the bounds of the grid
  • It is not a wall #
  • It has not been visited yet, i.e., dist[nx][ny] == -1

• Since reachability is guaranteed, the goal will always be reached during BFS.

  Source Code

import sys
from collections import deque

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

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

    dist = [[-1] * N for _ in range(N)]
    dist[sx][sy] = 1
    q = deque([(sx, sy)])

    directions = [(-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

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N:
                if grid[nx][ny] != '#' and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-xhigh.