[1194] 달이 차오른다, 가자.

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

1194번: 달이 차오른다, 가자.

<문제>

비트마스킹+bfs, 열쇠가 6개뿐이므로, 1<<6, 곧 64안에 전부 표현할 수 있다.

유의할 점은 visited[N][M][1<<6]으로 나타내주어야 한다. 단순히 개수가 중요한것이 아니라

'어느'열쇠를 갖고있는지가 중요하므로 [N][M][7]이 아닌 [N][M][1<<6]이 되겠다.

 

'1'이 여러개 존재할 수 있으며, 시작점인 '0'은 유일하다.

현재 상태는 {행, 열, 턴, (비트마스킹을 이용한)key}로 표현할 수 있으며

그 외에는 4방향 + 3차원 visited bfs를 구현하면 된다.

 

벽 부수고 이동하기에 비트마스킹을 곁들인 문제라 할 수 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, sy, sx, ey, ex, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[53][53];
bool visited[53][53][1 << 6];
typedef struct {
    int y, x, turn, key;
} state;
void bfs(void) {
    queue<state> q;
    q.push({sy, sx, 0, 0});
    visited[sy][sx][0] = true;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (a[cur.y][cur.x] == '1') {
            cout << cur.turn;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 1 || x < 1 || y > n || x > m) continue;
            if (a[y][x] == '#' || visited[y][x][cur.key] == true) continue;
            if (a[y][x] == '.' || a[y][x] == '0' || a[y][x] == '1') {
                visited[y][x][cur.key] = true;
                q.push({y, x, cur.turn + 1, cur.key});
            } else if ('a' <= a[y][x] && a[y][x] <= 'f') {
                int nKey = cur.key | (1 << (int)(a[y][x] - 'a'));
                q.push({y, x, cur.turn + 1, nKey});
                visited[y][x][nKey] = true;
            } else if ('A' <= a[y][x] && a[y][x] <= 'F') {
                int res = cur.key & (1 << (int)(a[y][x] - 'A'));
                if (res == 0) continue;
                q.push({y, x, cur.turn + 1, cur.key});
                visited[y][x][cur.key] = true;
            }
        }
    }
    cout << "-1";
}
int main(void) {
    cin >> n >> m;
    int i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '0') {
                sy = i;
                sx = j;
            }
        }
    }
    bfs();
    return 0;
}