BOJ. Move and break wall (2206)

Problem link

The maze is an N × M grid: 0 is an open cell and 1 is a wall. Starting at the upper-left cell, find the minimum number of cells in a path to the lower-right cell. You may break at most one wall. Count both the starting and destination cells; print -1 if no path exists.

A location alone is not a sufficient BFS state. Reaching the same cell with the wall-break still available can lead to routes that are impossible after the break has been used. Treat (cell, wallBroken) as the state, and mark each of the two states independently. From an unbroken state, an open neighbor keeps the state unbroken, while a wall neighbor is allowed only by consuming the break. From a broken state, only open neighbors are traversable.

The queue stores primitive integers: cellIndex * 2 + wallBrokenBit. Each state is enqueued at most once. BFS processes one distance layer at a time, starting at distance 1, so the destination’s distance is already the number of cells in the path. In particular, a one-cell maze immediately returns 1. The problem guarantees an open start and destination; the transition rule still correctly permits breaking an intervening wall, but never allows breaking a wall after the allowance is spent.

There are at most two states per cell. The time and space complexities are both O(NM).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer dimensions = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(dimensions.nextToken());
        int m = Integer.parseInt(dimensions.nextToken());

        char[][] maze = new char[n][m];
        for (int row = 0; row < n; row++) {
            maze[row] = in.readLine().toCharArray();
        }

        System.out.println(shortestPath(maze, n, m));
    }

    private static int shortestPath(char[][] maze, int n, int m) {
        int cells = n * m;
        boolean[] visited = new boolean[cells * 2];
        int[] queue = new int[cells * 2];
        int head = 0;
        int tail = 0;

        int startState = 0; // Cell 0, with the wall break unused.
        queue[tail++] = startState;
        visited[startState] = true;
        int distance = 1;

        while (head < tail) {
            int layerEnd = tail;
            while (head < layerEnd) {
                int state = queue[head++];
                int cell = state / 2;
                int wallBroken = state % 2;
                int row = cell / m;
                int col = cell % m;

                if (row == n - 1 && col == m - 1) {
                    return distance;
                }

                for (int direction = 0; direction < 4; direction++) {
                    int nextRow = row + DR[direction];
                    int nextCol = col + DC[direction];
                    if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= m) {
                        continue;
                    }

                    int nextWallBroken = wallBroken;
                    if (maze[nextRow][nextCol] == '1') {
                        if (wallBroken == 1) {
                            continue;
                        }
                        nextWallBroken = 1;
                    }

                    int nextCell = nextRow * m + nextCol;
                    int nextState = nextCell * 2 + nextWallBroken;
                    if (!visited[nextState]) {
                        visited[nextState] = true;
                        queue[tail++] = nextState;
                    }
                }
            }
            distance++;
        }

        return -1;
    }
}