1559번: 놀라운 미로
문제 MxN개의 칸으로 구성된 미로가 있다. 각 칸에는 4개의 인접한 곳으로 이동할 수 있는 문이 있다. 이 4개의 문은 한 번에 한 개만 열리며, A에서 B로 가는 문과 B에서 A로 가는 문은 별개로 작동한다. 문들의 초기 상태는 입력에서 주어지며, 1분에 한 번 시계 방향으로 90도씩 바뀐다. 미로에는 총 K개의 보물상자가 있다. 당신은 1분에 문이 열린 방향으로 한 칸 움직이거나 원하는 방향의 문이 열릴 때까지 기다릴 수 있다. 미로에서 당신이 시작
www.acmicpc.net
vst 차원을 2개 추가해야 했는데 문이 열리는 방향의 회전 주기 4의 차원이 그 중 하나다. 주기이므로 src 다음 지점은 src + 1 값으로 vst 처리를 해야 한다.
src 다음 지점을 vst[0][b][nr][nc]로 하기 위해서는 src 지점을 vst[3][b][nr][nc]로 해야 한다.
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int M, N, K;
int chToInt['W' + 1];
enum DIR {NORTH, EAST, SOUTH, WEST};
int door[100][100], box[100][100];
int vst[4][256][100][100];
struct qnode {
int r, c, b;
};
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int main() {
chToInt['N'] = NORTH;
chToInt['E'] = EAST;
chToInt['S'] = SOUTH;
chToInt['W'] = WEST;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for(int tc = 1; ; ++tc) {
cin >> M >> N;
if (M == 0 && N == 0) {
break;
}
for (int r = 0; r < M; ++r) {
for (int c = 0; c < N; ++c) {
char ch;
cin >> ch;
door[r][c] = chToInt[ch];
}
}
memset(box, -1, 100 * 100 * sizeof(int));
cin >> K;
for (int k = 0; k < K; ++k) {
int r, c;
cin >> r >> c;
box[r - 1][c - 1] = k;
}
int t = 0;
vst[3][0][0][0] = tc;
queue<qnode> q;
q.push({ 0, 0, 0 });
while (!q.empty()) {
int qs = q.size();
while (qs--) {
int r = q.front().r, c = q.front().c, b = q.front().b;
q.pop();
if (box[r][c] >= 0) {
b = b | (1 << box[r][c]);
}
if (b == (1 << K) - 1 && r == M - 1 && c == N - 1) {
goto out;
}
if (vst[t % 4][b][r][c] != tc) {
vst[t % 4][b][r][c] = tc;
q.push({ r, c, b });
}
int nr = r + dr[(door[r][c] + t) % 4], nc = c + dc[(door[r][c] + t) % 4];
if (nr < 0 || M <= nr || nc < 0 || N <= nc) {
continue;
}
if (vst[t % 4][b][nr][nc] != tc) {
vst[t % 4][b][nr][nc] = tc;
q.push({ nr, nc, b });
}
}
++t;
}
out:
cout << t << '\n';
}
return 0;
}