Overview

This is a problem where you move from start to goal on a grid and need to minimize the number of walls destroyed. We find the shortest path by treating the cost of moving to a passage as \(0\) and the cost of moving to a wall as \(1\).

Analysis

Essence of the Problem

Rephrasing this problem, it becomes: “Find the minimum cost path from \((1,1)\) to \((N,M)\), where the cost of passing through a passage is \(0\) and the cost of passing through a wall is \(1\).”

Naive Approach and Its Issues

This can be solved using Dijkstra’s algorithm, but since it uses a priority queue, the time complexity becomes \(O(NM \log(NM))\), which is somewhat heavy.

Insight Toward a More Efficient Solution

Notice that the edge weights are only of two types: \(0\) or \(1\). In such cases, we can use a special BFS called 0-1 BFS to find the shortest path with the same \(O(NM)\) time complexity as regular BFS.

Algorithm

What is 0-1 BFS?

It is a technique that efficiently solves the shortest path problem on graphs where edge weights are only \(0\) or \(1\), using a deque (double-ended queue).

How It Works

In regular BFS, vertices are processed in order of increasing distance. In 0-1 BFS, the processing order is controlled by the following rules:

1. If moving along an edge with cost \(0\) → add to the front of the deque
2. If moving along an edge with cost \(1\) → add to the back of the deque

This guarantees that we always process the vertex with the current minimum cost first.

Concrete Example

. # .
. # .
. . .

Consider the shortest path from \((0,0)\) to \((2,2)\) in this maze.

• Path without destroying any walls (down → down → right → right): cost \(0\)
• Path destroying one wall (right → down → down → right): cost \(1\)

In 0-1 BFS, since moves with cost \(0\) are processed with priority, the minimum cost is correctly computed.

Processing Flow

1. Initialize the distance array dist with \(\infty\), and set dist[0][0] = 0
2. Add the starting point \((0, 0)\) to the deque
3. Repeat the following until the deque is empty:
   • Remove vertex \((x, y)\) from the front
   • For each adjacent cell \((nx, ny)\) in the 4 directions:
     • Update if the new distance is less than the current distance
     • If it’s a passage (cost \(0\)), add to the front; if it’s a wall (cost \(1\)), add to the back

Complexity

• Time complexity: \(O(NM)\)
  • Because each cell is processed with its shortest distance at most once
• Space complexity: \(O(NM)\)
  • For the distance array and the deque

Implementation Notes

1. Using deque appropriately: In Python, use collections.deque, with appendleft() to add to the front and append() to add to the back.

2. Distance update condition: By updating only when new_dist < dist[nx][ny], we prevent processing the same cell multiple times.

3. Coordinate handling: The problem uses 1-indexed coordinates, but using 0-indexed in the implementation makes array access easier.

4. Direction vectors: Managing the 4 directions (up, down, left, right) with arrays dx, dy keeps the code clean.

   Source Code

from collections import deque

def solve():
    N, M = map(int, input().split())
    grid = [input().strip() for _ in range(N)]
    
    # 0-1 BFS を使用
    # 通路への移動はコスト0、壁への移動はコスト1
    INF = float('inf')
    dist = [[INF] * M for _ in range(N)]
    dist[0][0] = 0
    
    # deque を使った 0-1 BFS
    dq = deque()
    dq.append((0, 0))
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    while dq:
        x, y = dq.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < M:
                # 移動先が通路ならコスト0、壁ならコスト1
                cost = 0 if grid[nx][ny] == '.' else 1
                new_dist = dist[x][y] + cost
                
                if new_dist < dist[nx][ny]:
                    dist[nx][ny] = new_dist
                    if cost == 0:
                        dq.appendleft((nx, ny))
                    else:
                        dq.append((nx, ny))
    
    print(dist[N-1][M-1])

solve()

---

This editorial was generated by claude4.5opus.