BOJ. Marble Escape 2 (13460)

Problem: BOJ 13460 — Marble Escape 2 · 한국어 · 日本語

The board contains walls, one hole, and red and blue marbles. A tilt moves both marbles in one direction until each reaches a wall or falls into the hole. The goal is to get the red marble into the hole without letting the blue one fall, using at most 10 tilts.

A state is the pair of current cells (red, blue). From each state, try each of the four directions once. The marble farther toward the tilt direction must move first: otherwise the trailing marble could incorrectly stop the leading marble before it has moved. Roll the leading marble to its wall or the hole, then roll the trailing marble while treating the leading marble’s final cell as a blocker. A marble that falls into the hole is removed, so it no longer blocks the other one. This ordered motion prevents the marbles from overlapping. A tilt where neither marble changes cells is still a valid transition, but BFS visitation ensures it cannot cause an infinite loop.

Discard every state in which the blue marble falls. If only red falls, the current BFS distance is a successful answer. Otherwise enqueue the resulting pair if it has not been visited. BFS explores states in nondecreasing tilt count, so the first successful state uses the fewest tilts. Expanding only states below depth 10 enforces the limit; if none succeeds, print -1.

There are at most N * M possible cells per marble, hence O((NM)^2) position pairs; a direction rolls at most O(NM) cells. The board dimensions are at most 10 by 10, so this bounded state graph is small. The general transition bound is O(4 * NM) per state, with O((NM)^2) visited-state space.

C++17

#include <array>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct State {
    int red;
    int blue;
    int moves;
};

struct Roll {
    int cell;
    bool fell;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> board(n);
    int red = -1;
    int blue = -1;
    int hole = -1;
    for (int row = 0; row < n; ++row) {
        cin >> board[row];
        for (int col = 0; col < m; ++col) {
            const int cell = row * m + col;
            if (board[row][col] == 'R') red = cell;
            else if (board[row][col] == 'B') blue = cell;
            else if (board[row][col] == 'O') hole = cell;
        }
    }

    const array<int, 4> dr = {-1, 1, 0, 0};
    const array<int, 4> dc = {0, 0, -1, 1};
    vector<vector<bool>> visited(n * m, vector<bool>(n * m, false));
    queue<State> q;
    q.push({red, blue, 0});
    visited[red][blue] = true;

    auto roll = [&](int cell, int blocker, int direction) {
        int row = cell / m;
        int col = cell % m;
        while (true) {
            const int nextRow = row + dr[direction];
            const int nextCol = col + dc[direction];
            if (board[nextRow][nextCol] == '#' || nextRow * m + nextCol == blocker) {
                return Roll{row * m + col, false};
            }
            row = nextRow;
            col = nextCol;
            if (row * m + col == hole) return Roll{-1, true};
        }
    };

    while (!q.empty()) {
        const State current = q.front();
        q.pop();
        if (current.moves == 10) continue;

        for (int direction = 0; direction < 4; ++direction) {
            const int redCoordinate = direction < 2 ? current.red / m : current.red % m;
            const int blueCoordinate = direction < 2 ? current.blue / m : current.blue % m;
            const bool redFirst = (direction == 0 || direction == 2)
                                      ? redCoordinate < blueCoordinate
                                      : redCoordinate > blueCoordinate;

            const Roll first = redFirst
                                   ? roll(current.red, current.blue, direction)
                                   : roll(current.blue, current.red, direction);
            const int firstCell = first.fell ? -1 : first.cell;
            const Roll second = redFirst
                                    ? roll(current.blue, firstCell, direction)
                                    : roll(current.red, firstCell, direction);

            const bool redFell = redFirst ? first.fell : second.fell;
            const bool blueFell = redFirst ? second.fell : first.fell;
            if (blueFell) continue;
            if (redFell) {
                cout << current.moves + 1 << '\n';
                return 0;
            }

            const int nextRed = redFirst ? first.cell : second.cell;
            const int nextBlue = redFirst ? second.cell : first.cell;
            if (!visited[nextRed][nextBlue]) {
                visited[nextRed][nextBlue] = true;
                q.push({nextRed, nextBlue, current.moves + 1});
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}