Overview

Given an \(N \times N\) grid maze, the problem asks to find the number of cells (including both endpoints) on the shortest path from start S to goal G. This can be solved using a typical Breadth-First Search (BFS).

Analysis

• Takahashi can move one cell at a time in the four cardinal directions (up, down, left, right), and each move has a uniform cost (1 step).
• Shortest path problems on graphs where all edge weights are equal can be efficiently solved with BFS (Breadth-First Search).
• A naive approach of enumerating all paths (exhaustive search with DFS) would cause the number of paths to explode exponentially, resulting in TLE. By using BFS, each cell is visited at most once, allowing us to efficiently find the shortest distance.

Why does BFS find the shortest path?

BFS explores cells in order of increasing distance from the start (distance 0 → distance 1 → distance 2 → …). The distance at which a cell is first reached is the shortest distance to that cell. This is an important property that holds when all edge weights are equal.

Concrete Example

5
S....
.###.
.#G#.
.#..#
.....

In this example, BFS finds that the shortest distance from S(1,1) to G(3,3) is 8 moves, so the number of cells visited is \(8 + 1 = 9\).

Algorithm

1. Read the input and record the coordinates of S and G.
2. Initialize the distance array dist with \(-1\) (unvisited), and set dist[sx][sy] = 0.
3. Enqueue the start position and begin BFS.
4. Dequeue a cell \((x, y)\) and for each adjacent cell \((nx, ny)\) in the four cardinal directions:
   • If it is within the grid bounds, is not a wall, and has not been visited yet, set dist[nx][ny] = dist[x][y] + 1 and enqueue it.
5. When the goal is reached, output dist[gx][gy] + 1 (since dist records the number of moves = number of edges, we add \(+1\) to get the number of cells).

Visualization of BFS Operation

Distance from start S:
0  1  2  3  4
1  #  #  #  5
2  #  ?  #  6
3  #  9  8  #
4  5  6  7  ...

Since cells are explored in order of increasing distance, the first time the goal is reached corresponds to the shortest path.

Complexity

• Time complexity: \(O(N^2)\)
  • Since each cell is visited at most once, the total number of operations is at most \(N^2\).
• Space complexity: \(O(N^2)\)
  • Storing the grid, the distance array dist, and the BFS queue each require \(O(N^2)\) space.

Implementation Notes

• Use deque (double-ended queue): By using Python’s collections.deque, removing from the front of the queue (popleft) takes \(O(1)\). Using pop(0) on a regular list takes \(O(N)\) and can cause TLE.

• Difference between distance and number of cells visited: The dist array records the “number of moves (number of edges).” Since the problem asks for the “number of cells visited,” we need to add \(+1\) at the end (e.g., 3 moves → 4 cells visited).

• Early termination: By immediately outputting the answer and terminating as soon as the goal is reached, unnecessary exploration can be avoided.

  Source Code

from collections import deque

def main():
    N = int(input())
    grid = []
    sx = sy = gx = gy = 0
    for i in range(N):
        row = input()
        grid.append(row)
        for j in range(N):
            if row[j] == 'S':
                sx, sy = i, j
            elif row[j] == 'G':
                gx, gy = i, j

    dist = [[-1] * N for _ in range(N)]
    dist[sx][sy] = 0
    queue = deque([(sx, sy)])
    while queue:
        x, y = queue.popleft()
        if x == gx and y == gy:
            print(dist[x][y] + 1)
            return
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and grid[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))

    print(dist[gx][gy] + 1)

main()

---

This editorial was generated by claude4.6opus-thinking.