[4991] 로봇 청소기

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

"[17244] 아맞다우산"과 거의 동일한 문제다.

방문처리를 (행, 열, 비트)로 두고, 비트에 S개의 쓰레기를 처리한 여부를 [0, 1<<S)로 놓는다.

각 쓰레기가 구분되어있지 않으므로, 편의상 '*'대신 a[i][j]= '0' + S++;를 통해 [0, S)로 넘버링해주고 bfs를 돌려준다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};

int n, m, S;

char a[22][22];

bool vst[22][22][1 << 10];

typedef struct {

    int y, x, bt, turn;

} state;

int f(int sy, int sx) {

    queue<state> q;

    q.push({sy, sx, 0, 0});

    memset(vst, 0, sizeof(vst));

    vst[sy][sx][0] = true;

    while (!q.empty()) {

        state cur = q.front();

        q.pop();

        if ('0' <= a[cur.y][cur.x] && a[cur.y][cur.x] <= '0' + S)

            cur.bt |= (1 << (a[cur.y][cur.x] - '0'));

        if (cur.bt == (1 << S) - 1) return cur.turn;

        for (int i = 0; i < 4; i++) {

            int y = cur.y + dy[i];

            int x = cur.x + dx[i];

            if (y < 0 || x < 0 || y >= n || x >= m) continue;

            if (a[y][x] == 'x') continue;

            if (vst[y][x][cur.bt] == false) {

                vst[y][x][cur.bt] = true;

                q.push({y, x, cur.bt, cur.turn + 1});

            }

        }

    }

    return -1;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    while (1) {

        cin >> m >> n;

        if (m == 0 && n == 0) break;

        memset(a, 0, sizeof(a));

        S = 0;

        int i, j, sy, sx;

        for (i = 0; i < n; i++) {

            for (j = 0; j < m; j++) {

                cin >> a[i][j];

                if (a[i][j] == 'o') {

                    sy = i, sx = j;

                    a[i][j] = '.';

                }

                if (a[i][j] == '*') a[i][j] = '0' + S++;

            }

        }

        cout << f(sy, sx) << '\n';

    }

    return 0;

}

---