bfs를 이용한 문제이다. 이번 문제는 기존 bfs와 다르게 주어지는 맵이 3차원으로 이루어져 있다. 그래서 이동 방향이 동,서,남,북,상,하 6가지가 된다. 맵을 입력받을 때 S
와 E
를 찾아 위치를 저장해주고 bfs를 돌려준다. 최초로 E
좌표에 도착했을 때가 가장 먼저 도착한 순간이므로 이 때의 count
를 result
에 저장해 출력해주었다. 문제 자체는 어렵지 않았는데 이번에는 출력 부분에서 문제가 있었다. Escaped in 11 minute(s).
형식으로 출력해야하는데 끝에 .
을 빼먹은 것을 모르고 좀 해맸었다... 출력도 자세히 봐야겠다. 문제를 랜덤으로 풀다보니 요즘 bfs 문제를 많이 풀게됬다. bfs는 확실히 푸는 속도가 붙은 것 같아 기분이 좋다 ^^
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int L, R, C;
int ls, rs, cs;
int le, re, ce;
string A[30][30];
bool check[30][30][30];
int dl[] = { 0,0,0,0,-1,1 };
int dr[] = { -1,1,0,0,0,0 };
int dc[] = { 0,0,-1,1,0,0 };
int result = -1;
void init() {
memset(check, false, sizeof(check));
result = -1;
}
void bfs() {
queue <pair<pair<int, int>, pair<int, int>>> q;
q.push({ {0,ls},{rs,cs} });
check[ls][rs][cs] = true;
while (!q.empty()) {
int count = q.front().first.first;
int l = q.front().first.second;
int r = q.front().second.first;
int c = q.front().second.second;
if (l == le && r == re && c == ce) {
result = count;
break;
}
q.pop();
for (int i = 0; i < 6; i++) {
int nl = l + dl[i];
int nr = r + dr[i];
int nc = c + dc[i];
if (nl < 0 || nr < 0 || nc < 0 || nl >= L || nr >= R || nc >= C) continue;
if (check[nl][nr][nc]) continue;
if (A[nl][nr][nc] == '#') continue;
q.push({ { count + 1,nl }, { nr,nc } });
check[nl][nr][nc] = true;
}
}
}
void solution() {
bfs();
if (result == -1) {
cout << "Trapped!" << endl;
}
else {
cout << "Escaped in " << result << " minute(s)." << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
while (1) {
init();
cin >> L >> R >> C;
if (L == 0 && R == 0 && C == 0) break;
for (int i = 0; i < L; i++) {
for (int j = 0; j < R; j++) {
string s;
cin >> s;
for (int k = 0; k < s.size(); k++) {
if (s[k] == 'S') {
ls = i;
rs = j;
cs = k;
}
else if (s[k] == 'E') {
le = i;
re = j;
ce = k;
}
}
A[i][j] = s;
}
}
solution();
}
return 0;
}