백준 1035번 - 조각 움직이기

On this page

BOJ 1035: Moving Pieces

Approach: breadth-first search over configurations

The board has 25 cells, and the problem has at most five pieces. A state must describe the positions of all pieces: whether each cell is occupied. Encode that configuration as a 25-bit integer, with bit r * 5 + c set exactly when cell (r, c) contains a piece. The pieces are indistinguishable, so this representation has no ordering ambiguity.

An edge in the state graph is exactly one legal move: choose an occupied cell, then move its piece to an orthogonally adjacent cell that is empty. This restriction matters. Assigning final cells and summing Manhattan distances is not sufficient: independently shortest routes can collide, and a set of destinations alone does not prove those destinations can be reached in the required number of legal moves.

A goal state is one in which every piece belongs to the same four-neighbor-connected component. Starting from any occupied cell, flood-fill through occupied neighbors and compare the number reached with the total number of pieces.

Run BFS from the input configuration, marking each mask visited when it is enqueued. Every edge has cost one, so BFS visits states in nondecreasing move count; the first goal it removes from the queue therefore has the minimum number of moves. The original positions are already a valid state, so a goal input returns zero.

There are at most

$\sum_{k=1}^{5} \binom{25}{k} = 68{,}405$

nonempty configurations with at most five pieces. An unordered_set stores only reached masks, rather than allocating a distance table for all $2^{25}$ possible masks. Each state has at most 20 candidate directed moves (five pieces, at most four neighbors).

C++17

#include <array>
#include <cstdint>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
#include <utility>

using namespace std;

using Mask = uint32_t;

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

    array<uint32_t, 25> neighbors{};
    for (int r = 0; r < 5; ++r) {
        for (int c = 0; c < 5; ++c) {
            const int cell = r * 5 + c;
            if (r > 0) neighbors[cell] |= uint32_t{1} << (cell - 5);
            if (r < 4) neighbors[cell] |= uint32_t{1} << (cell + 5);
            if (c > 0) neighbors[cell] |= uint32_t{1} << (cell - 1);
            if (c < 4) neighbors[cell] |= uint32_t{1} << (cell + 1);
        }
    }

    Mask start = 0;
    for (int r = 0; r < 5; ++r) {
        string row;
        cin >> row;
        for (int c = 0; c < 5; ++c) {
            if (row[c] == '*') start |= Mask{1} << (r * 5 + c);
        }
    }

    auto isConnected = [&](Mask pieces) {
        const int pieceCount = __builtin_popcount(pieces);
        Mask reached = 0;
        Mask frontier = pieces & (~pieces + 1);  // lowest occupied bit
        while (frontier != 0) {
            const int cell = __builtin_ctz(frontier);
            const Mask bit = Mask{1} << cell;
            frontier &= ~bit;
            if (reached & bit) continue;
            reached |= bit;
            frontier |= neighbors[cell] & pieces & ~reached;
        }
        return __builtin_popcount(reached) == pieceCount;
    };

    queue<pair<Mask, int>> q;
    unordered_set<Mask> visited;
    q.push({start, 0});
    visited.insert(start);

    while (!q.empty()) {
        const auto [state, moves] = q.front();
        q.pop();

        if (isConnected(state)) {
            cout << moves << '\n';
            return 0;
        }

        for (Mask pieces = state; pieces != 0; pieces &= pieces - 1) {
            const int from = __builtin_ctz(pieces);
            const Mask fromBit = Mask{1} << from;
            Mask destinations = neighbors[from] & ~state;
            while (destinations != 0) {
                const int to = __builtin_ctz(destinations);
                const Mask toBit = Mask{1} << to;
                destinations &= ~toBit;

                const Mask next = (state & ~fromBit) | toBit;
                if (visited.insert(next).second) q.push({next, moves + 1});
            }
        }
    }
}

The grid is connected, and a piece can be moved through empty cells, so a connected arrangement is reachable. Thus the queue eventually finds a goal for every valid input.