Overview

Given an \(N \times N\) grid maze, the problem asks to find the number of cells on the shortest path from the start cell S to the goal cell G.

Analysis

This problem can be viewed as a shortest path problem on a graph where all movement costs are \(1\).

1. Finding the Shortest Path: When finding the shortest path on a grid, depth-first search (DFS) does not guarantee shortest paths and can be inefficient. On the other hand, using breadth-first search (BFS), the search proceeds in order from cells closest to the start, so the first path found to the goal is always the shortest.
2. Definition of “Number of Cells”: The problem asks for “the number of cells on the path (including start and goal).” If we let \(D\) denote the “number of moves (number of edges)” typically obtained by BFS, then the number of cells traversed is \(D + 1\).
3. Checking Constraints: Since \(N \leq 500\), the total number of cells is \(N^2 = 250,000\). BFS visits each cell at most once, so the time complexity is \(O(N^2)\), which is well within the time limit.

Algorithm

We use Breadth-First Search (BFS).

1. Preparation:
   • Prepare a 2-dimensional array dist to record the shortest distance to each cell, initialized to \(-1\) to indicate unvisited.
   • Prepare a queue to manage search candidates, and enqueue the coordinates of the start cell. Set the distance of the start cell to dist[start] = 0.
2. Search:
   • Repeat the following operations until the queue is empty:
     1. Dequeue the current cell \((r, c)\) from the queue.
     2. Examine the 4 adjacent directions (up, down, left, right) from that cell.
     3. If an adjacent cell \((nr, nc)\) satisfies all the conditions: “is within the grid,” “is not a wall (#),” and “has not been visited yet (dist == -1),” then enqueue that cell and update the distance as dist[nr][nc] = dist[r][c] + 1.
3. Termination:
   • The moment the goal cell is reached, output the distance \(D\) at that point plus \(1\), and terminate.

Complexity

• Time Complexity: \(O(N^2)\)
  • Scanning all cells of the grid to find the start and goal takes \(O(N^2)\), and visiting each cell at most once during BFS takes \(O(N^2)\).
• Space Complexity: \(O(N^2)\)
  • \(O(N^2)\) memory is used for the 2-dimensional arrays storing the grid information and distances.

Implementation Tips

• Efficient Queue Operations: In Python, list.pop(0) takes \(O(N)\), so use collections.deque to allow \(O(1)\) element retrieval.

• Generalizing Movement: By preparing arrays such as dr = [0, 0, 1, -1] and dc = [1, -1, 0, 0] and iterating over them in a loop, the movement processing for all four directions can be written concisely.

• Reading Input: Since \(N\) can be large and each row of the maze is given as a string, it is necessary to parse them appropriately and identify the coordinates.

  Source Code

import sys
from collections import deque

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    grid = input_data[1:]

    start_pos = None
    goal_pos = None
    
    # スタートとゴールの位置を特定
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 'S':
                start_pos = (r, c)
            elif grid[r][c] == 'G':
                goal_pos = (r, c)

    # 幅優先探索 (BFS)
    queue = deque([start_pos])
    # dist[r][c] はスタート地点からの最小移動回数
    dist = [[-1] * n for _ in range(n)]
    dist[start_pos[0]][start_pos[1]] = 0

    # 移動方向（上下左右）
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]

    while queue:
        r, c = queue.popleft()

        # ゴールに到達した場合
        if (r, c) == goal_pos:
            # 経路上のマスの数は (移動回数 + 1)
            print(dist[r][c] + 1)
            return

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            
            # グリッドの範囲内かつ壁ではなく、未訪問のマスであるか確認
            if 0 <= nr < n and 0 <= nc < n:
                if grid[nr][nc] != '#' and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.