Overview

A problem on a grid maze where you need to minimize the number of walls that must be destroyed when moving from the start position to the goal position.

Analysis

In this problem, you need not only to find a path from the start to the goal, but also to choose a “path with the fewest wall destructions” depending on “which walls to destroy.”

As a naive approach, you might think of Breadth-First Search (BFS), but this is an algorithm that minimizes the “number of moves,” and it is not suitable for minimizing the “number of wall destructions,” which is our objective here. For example, a path with fewer moves but requiring many wall destructions may not be optimal.

What we want to consider instead is a method that explores while managing the “minimum number of wall destructions to reach each cell.” This can be viewed as a shortest distance problem on a weighted graph, and Dijkstra’s algorithm is effective.

Specifically: - Consider each cell as a vertex of the graph. - Treat movement to adjacent cells as edges, with cost 0 if the destination is a passage, and cost 1 if it is a wall. - By setting costs this way, Dijkstra’s algorithm can find the “minimum cost from start to goal (= minimum number of wall destructions).”

Algorithm

This problem can be solved by treating the grid as a graph and using Dijkstra’s algorithm to find the shortest path (= minimum number of wall destructions).

Steps

1. Prepare a two-dimensional array dist to record the minimum cost (number of wall destructions) to reach each cell \((i, j)\), initialized to infinity.
2. Set the cost of the start position \((0, 0)\) to 0, and add \((0, 0, 0)\) to a priority queue (heap).
3. Extract the cell with the minimum cost from the queue, and attempt to move to adjacent cells in all four directions (up, down, left, right).
4. If the destination is:
   • A passage, move with cost 0.
   • A wall, move with cost 1 (destroy it).
5. If the cost after moving is less than the already recorded cost, update it and add to the queue.
6. When the goal \((N-1, M-1)\) is reached, the cost at that point is the answer.

In this way, we leverage the fact that movement costs are either 0 or 1 and use Dijkstra’s algorithm to find the shortest path.

Complexity

• Time complexity: \(O(NM \log(NM))\)
• Space complexity: \(O(NM)\)

Here, \(N, M\) are the number of rows and columns of the grid, respectively. In Dijkstra’s algorithm, priority queue operations incur a \(\log\) factor, resulting in the above overall complexity.

Implementation Notes

• Since the grid size is at most \(500 \times 500\), Dijkstra’s algorithm is fast enough in terms of complexity.

• Manage the cost of each cell with a two-dimensional array called dist, initialized to float('inf').

• Insert tuples of (cost, row, col) into the priority queue, extracting them in order of smallest cost.

• The key part is changing the cost to 0 or 1 depending on whether the destination is a wall.

• Since the same cell may be added to the queue multiple times, a check to skip when dist[x][y] < cost is necessary.

  Source Code

import heapq
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    S = data[2:2+N]
    
    # グリッドのコストを管理する二次元配列
    dist = [[float('inf')] * M for _ in range(N)]
    dist[0][0] = 0
    
    # ダイクストラ法用の優先度付きキュー
    queue = [(0, 0, 0)]  # (cost, row, col)
    
    # 移動方向（上下左右）
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        cost, x, y = heapq.heappop(queue)
        
        # 現在のコストが既に記録されているコストより大きい場合はスキップ
        if cost > dist[x][y]:
            continue
        
        # 各方向への移動を試す
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # グリッド範囲外のチェック
            if 0 <= nx < N and 0 <= ny < M:
                # 壁ならコスト1、通路ならコスト0
                new_cost = cost + (1 if S[nx][ny] == '#' else 0)
                
                # 新しいコストが現在の記録より小さければ更新してキューに追加
                if new_cost < dist[nx][ny]:
                    dist[nx][ny] = new_cost
                    heapq.heappush(queue, (new_cost, nx, ny))
    
    # 右下のマスまでの最小コストを出力
    print(dist[N-1][M-1])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.