백준 4991번 로봇 청소기 — BFS와 비트마스크 DP C++ 풀이

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

const int INF = 1'000'000;
const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};

struct Point {
    int y, x;
};

int width, height;
vector<string> room;
vector<Point> points;  // 0번은 로봇, 1번부터 먼지
vector<vector<int>> pairDistance;
int memo[11][1 << 10];

vector<vector<int>> bfs(Point start) {
    vector<vector<int>> distance(height, vector<int>(width, -1));
    queue<Point> q;

    distance[start.y][start.x] = 0;
    q.push(start);

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        for (int dir = 0; dir < 4; ++dir) {
            int ny = current.y + dy[dir];
            int nx = current.x + dx[dir];

            if (ny < 0 || ny >= height || nx < 0 || nx >= width) continue;
            if (room[ny][nx] == 'x' || distance[ny][nx] != -1) continue;

            distance[ny][nx] = distance[current.y][current.x] + 1;
            q.push({ny, nx});
        }
    }

    return distance;
}

int solve(int current, int mask) {
    int dirtCount = static_cast<int>(points.size()) - 1;
    int allCleaned = (1 << dirtCount) - 1;
    if (mask == allCleaned) return 0;

    int& cached = memo[current][mask];
    if (cached != -1) return cached;

    cached = INF;
    for (int next = 1; next < static_cast<int>(points.size()); ++next) {
        int bit = 1 << (next - 1);
        if (mask & bit) continue;
        if (pairDistance[current][next] == -1) continue;

        cached = min(
            cached,
            pairDistance[current][next] + solve(next, mask | bit)
        );
    }
    return cached;
}

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

    while (cin >> width >> height && (width != 0 || height != 0)) {
        room.resize(height);
        points.clear();
        vector<Point> dirt;

        Point robot{};
        for (int y = 0; y < height; ++y) {
            cin >> room[y];
            for (int x = 0; x < width; ++x) {
                if (room[y][x] == 'o') robot = {y, x};
                if (room[y][x] == '*') dirt.push_back({y, x});
            }
        }

        points.push_back(robot);
        points.insert(points.end(), dirt.begin(), dirt.end());

        int pointCount = static_cast<int>(points.size());
        pairDistance.assign(pointCount, vector<int>(pointCount, -1));

        for (int i = 0; i < pointCount; ++i) {
            vector<vector<int>> distance = bfs(points[i]);
            for (int j = 0; j < pointCount; ++j) {
                pairDistance[i][j] = distance[points[j].y][points[j].x];
            }
        }

        memset(memo, -1, sizeof(memo));
        int answer = solve(0, 0);
        cout << (answer >= INF ? -1 : answer) << '\n';
    }
}