문제:
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
www.acmicpc.net
코드:
#include <iostream>
#include <queue>
#define f(i, n) for(int i = 1; i <= (n); ++i)
using namespace std;
int N, M;
char mz[52][52];
bool vst[51][51][1 << 6];
struct qnode {
int n, m, b;
};
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
queue<qnode> q;
fill(mz[0], mz[0] + M + 2, '#');
f(n, N){
mz[n][0] = mz[n][M + 1] = '#';
f(m, M) {
cin >> mz[n][m];
if (mz[n][m] == '0') {
mz[n][m] = '.';
vst[n][m][0] = 1;
q.push({ n, m, 0 });
}
}
}
fill(mz[N + 1], mz[N + 1] + M + 2, '#');
int t = 0;
while (!q.empty()) {
int qs = q.size();
while (qs--) {
qnode pt = q.front(); q.pop();
char obj = mz[pt.n][pt.m];
if (obj == '1')
goto suc;
if ('a' <= obj && obj <= 'f')
pt.b |= (1 << (obj - 'a'));
for (int d = 0; d < 4; ++d) {
int cn = pt.n + dn[d], cm = pt.m + dm[d];
char cobj = mz[cn][cm];
if (cobj == '#') continue;
if ('A' <= cobj && cobj <= 'F' && !(pt.b & (1 << (cobj - 'A')))) continue;
if (vst[cn][cm][pt.b]) continue;
vst[cn][cm][pt.b] = 1;
q.push({ cn, cm, pt.b });
}
}
++t;
}
t = -1;
suc:
cout << t;
return 0;
}