Overview

In a maze composed of an \(N \times M\) grid, this is a shortest path problem where we move from start to goal while minimizing the number of walls (#) destroyed.

Analysis

This problem can be solved as a shortest path problem by treating the grid as a graph. Each cell is considered a “vertex,” and movement to adjacent cells is considered an “edge.”

We define the cost of movement as follows: - If the destination cell is a passage (.): cost \(0\) - If the destination cell is a wall (#): cost \(1\) (because we destroy the wall to turn it into a passage)

With this definition, the answer we seek is “the minimum cost from cell \((1, 1)\) to cell \((N, M)\).”

For a normal maze (where all movement costs are \(1\)), breadth-first search (BFS) would suffice, but since there are \(2\) types of costs, \(0\) and \(1\), a simple queue-based BFS cannot compute the correct answer. In this special situation where “edge weights are only \(0\) or \(1\),” we can efficiently find the shortest path using an algorithm called 0-1 BFS.

Algorithm

0-1 BFS

0-1 BFS is a technique that finds shortest distances using a double-ended queue (deque).

1. Initialization: Initialize the distance array dist to infinity, and set the distance of the starting point to \(0\).
2. Exploration: Pop the current cell from the front of the deque and examine the \(4\) adjacent directions.
3. Update:
   • If the cost to the destination is \(0\) (passage):
     • If the distance can be improved with the current distance, update dist and add that cell to the front (left) of the deque.
   • If the cost to the destination is \(1\) (wall):
     • If the distance can be improved with the current distance \(+1\), update dist and add that cell to the back (right) of the deque.
4. Termination: Repeat until the deque is empty or the goal is reached.

By prioritizing exploration of cost \(0\) movements, this works like a simplified version of Dijkstra’s algorithm, finding the shortest path while keeping the computational complexity low.

Complexity

• Time complexity: \(O(N \times M)\)
  • Since each cell is popped from the deque at most once, the algorithm finishes in time proportional to the number of cells in the grid.
• Space complexity: \(O(N \times M)\)
  • The array holding the grid state and the array dist holding the shortest distance for each cell each use \(N \times M\) memory.

Implementation Notes

• Using deque: In Python, use collections.deque. The key point is to use appendleft() for cost \(0\) and append() for cost \(1\).

• Boundary check: Always verify that the destination cell is within the range \(0 \le r < N\) and \(0 \le c < M\).

• Early termination: In 0-1 BFS, when a cell is popped from the deque, its shortest distance is finalized. Therefore, we can output the answer and terminate the moment the goal cell is popped.

  Source Code

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込み、空白や改行で分割します。
    # これにより、N, M およびグリッドの各行を効率的に取得できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 行数, M: 列数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # グリッドの状態を文字列のリストとして取得します
    grid = input_data[2:]
    
    # 各マスに到達するために破壊した壁の最小数を保持する2次元配列
    # 初期値として十分に大きな値（無限大）を設定します
    inf = 10**9
    dist = [[inf] * M for _ in range(N)]
    
    # スタート地点 (0, 0) のコストは 0 です
    dist[0][0] = 0
    
    # 0-1 BFS（最短経路アルゴリズムの一種）のためのデック
    # (行, 列) のタプルを格納します
    dq = deque([(0, 0)])
    
    # 移動可能な4方向（右、左、下、上）
    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
    
    while dq:
        # デックの先頭から現在のマスを取り出します
        r, c = dq.popleft()
        d = dist[r][c]
        
        # ゴール地点 (N-1, M-1) に到達した場合、その時点のコストを出力して終了します
        # 0-1 BFSでは、最初に取り出したときがそのマスへの最短経路となります
        if r == N - 1 and c == M - 1:
            print(d)
            return
        
        # 隣接する4マスを探索します
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # グリッドの範囲内であるか確認します
            if 0 <= nr < N and 0 <= nc < M:
                # 移動先のマスが壁（#）なら破壊コスト 1、通路（.）ならコスト 0
                weight = 1 if grid[nr][nc] == '#' else 0
                
                # より少ない壁破壊数でそのマスに到達できる場合、更新を行います
                if dist[nr][nc] > d + weight:
                    dist[nr][nc] = d + weight
                    
                    if weight == 0:
                        # コスト 0 の移動はデックの先頭に追加し、優先的に探索します
                        dq.appendleft((nr, nc))
                    else:
                        # コスト 1 の移動はデックの末尾に追加します
                        dq.append((nr, nc))

if __name__ == '__main__':
    solve()

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