Overview

This is a problem where you need to find the minimum cost (number of walls destroyed) to travel from \((1,1)\) to \((N,M)\) in a maze where a cost of \(+1\) is incurred only when entering a wall cell. Since the cost of each move is either \(0\) or \(1\), we use 0-1 BFS to find the shortest path.

Analysis

• Regardless of which path you take, there is no limit on the number of moves itself; what we want to minimize is the “number of walls destroyed.”
• When moving from a cell to an adjacent cell:
  • If the destination is ., the additional cost is \(0\)
  • If the destination is #, the additional cost is \(1\) (since we break through it)
• In other words, this problem is a weighted shortest path problem where each cell is a vertex and up/down/left/right movements are edges (with edge weights of \(0\) or \(1\)).

If we naively run BFS for “minimum number of moves,” it does not guarantee that the number of walls destroyed is minimized.
For example, a path that takes fewer moves but destroys many walls may be worse than a longer detour that destroys no walls.

For general weighted shortest paths, we would use Dijkstra’s algorithm, but since the weights in this problem are limited to \(0/1\), we can use 0-1 BFS (\(O(E)\)), which is faster than Dijkstra with a heap (\(O(E\log V)\)).

Algorithm

We use 0-1 BFS to compute the “minimum number of destructions” dist for each cell.

• Start with dist[start]=0 and prepare a double-ended queue deque.
• Dequeue a vertex \(v\) and examine its up/down/left/right neighbors \(nv\).
• The additional cost \(w\) is “1 if the destination is a wall, 0 if it is a passage”:
  • w = 1 if grid[nr][nc] == '#' else 0
• If dist[nv] > dist[v] + w, update it, and:
  • If \(w=0\), push to the front of the deque (to process it with higher priority)
  • If \(w=1\), push to the back of the deque
• By repeating this, states closest to the currently known minimum cost are always processed first, ensuring the shortest path is computed correctly.

Since the number of vertices \(NM\) can be large in this problem, the implementation converts each cell \((r,c)\) to a one-dimensional index v = r*M + c and stores values in an array for efficiency.

Complexity

• Time complexity: \(O(NM)\)
  (Each edge is updated at most a constant number of times, and the entire 0-1 BFS runs in \(O(V+E)\). For a grid, \(V=NM,\ E\approx 4NM\))
• Space complexity: \(O(NM)\)
  (For the distance array, deque, etc.)

Implementation Notes

• 0-1 BFS: The key idea is to use appendleft for weight-\(0\) transitions and append for weight-\(1\) transitions.

• To handle \(N,M\le 500\) (up to \(250{,}000\) cells) in Python:

  • The grid is read as bytes, and '#' is compared as 35 (ord('#'))

  • dist is stored as a one-dimensional array instead of two-dimensional (index calculation uses divmod(v, M)) These optimizations reduce the constant factor.

    Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    grid = [next(it) for _ in range(N)]  # bytes

    INF = 10**9
    size = N * M
    dist = [INF] * size

    start = 0
    goal = size - 1
    dist[start] = 0
    dq = deque([start])

    while dq:
        v = dq.popleft()
        dv = dist[v]
        r, c = divmod(v, M)

        nr = r - 1
        if nr >= 0:
            nv = v - M
            w = 1 if grid[nr][c] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nr = r + 1
        if nr < N:
            nv = v + M
            w = 1 if grid[nr][c] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nc = c - 1
        if nc >= 0:
            nv = v - 1
            w = 1 if grid[r][nc] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nc = c + 1
        if nc < M:
            nv = v + 1
            w = 1 if grid[r][nc] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

    sys.stdout.write(str(dist[goal]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.