BOJ)1194 달이 차오른다, 가자.

문제: icpc.me/1194

가중치 없는 그래프에서의 최단거리를 구해야 하므로 BFS를 이용하면 된다,

이때 열쇠라는 조건이 추가로 붙는데 우리는 열쇠를 쥐고 있는 상태를 비트마스킹을 통하여 표현해주면 된다.

qu의 3번째 인자는 해당 상태가 가지는 열쇠를 비트로 표현한 것이다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m, disc[51][51][1 << 7];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
char a[51][51];
int sx, sy;
bool chk(int x, int y) {
    return 0 <= x&&x < n && 0 <= y&&y < m;
}
int bfs() {
    queue<pair<pair<int, int>, int>> qu;
    disc[sx][sy][0] = 1;
    qu.push({ {sx,sy},0 });
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int x = qu.front().first.first;
            int y = qu.front().first.second;
            int z = qu.front().second;
            qu.pop();
            if (a[x][y] == '1')return ret;
            for (int i = 0; i < 4; i++) {
                int cx = x + dx[i];
                int cy = y + dy[i];
                if (!chk(cx, cy) || a[cx][cy] == '#')
                    continue;
                if ('a' <= a[cx][cy] && a[cx][cy] <= 'f') {
                    int cz = z | (1 << (a[cx][cy] - 'a'));
                    if (disc[cx][cy][cz])continue;
                    disc[cx][cy][cz] = 1;
                    qu.push({ {cx,cy} ,cz });
                }
                else if ('A' <= a[cx][cy] && a[cx][cy] <= 'Z'&&!disc[cx][cy][z]) {
                    if (z&(1 << a[cx][cy] - 'A')) {
                        disc[cx][cy][z] = 1;
                        qu.push({ {cx,cy},z });
                    }
                }
                else if (!disc[cx][cy][z]) {
                    disc[cx][cy][z] = 1;
                    qu.push({ {cx,cy},z });
                }
            }
        }
        ret++;
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c", &a[i][j]);
            if (a[i][j] == '0') {
                sx = i, sy = j;
            }
        }
    }
    printf("%d\n", bfs());
    return 0;
}