[백준-6087] 상범 빌딩


3차원의 그래프 문제로서의 확장이다.

상범이가 갈 수 있는 방향은 당연히 앞뒤양옆위아래 6가지.

이 부분만 고려하면 여느 BFS 문제와 비슷하다.

Code


#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct zyxm {
	int z, y, x, m;
};

int L, R, C, ans;
char map[30][30][30];
bool check[30][30][30];
const int dy[] = { 0,0,-1,1,0,0 }, dx[] = { 0,0,0,0,-1,1 }, dz[] = { -1,1,0,0,0,0 };

void bfs(zyxm start) {
	check[start.z][start.y][start.x] = true;
	queue<zyxm> q;
	q.push(start);
	while (!q.empty()) {
		int cz = q.front().z;
		int cy = q.front().y;
		int cx = q.front().x;
		int cm = q.front().m;
		q.pop(); 
		if (map[cz][cy][cx] == 'E') {
			ans = cm;
			break;
		}
		for (int dir = 0; dir < 6; dir++) {
			int nz = cz + dz[dir];
			int ny = cy + dy[dir];
			int nx = cx + dx[dir];
			if (nz<0 || nz>L - 1 || ny<0 || ny>R - 1 || nx<0 || nx>C - 1) continue;
			if (map[nz][ny][nx] != '#' && !check[nz][ny][nx]) {
				q.push({ nz,ny,nx,cm + 1 });
				check[nz][ny][nx] = true;
			}
		}
	}
}

int main() {
	while (1) {
		ans = 0;
		zyxm start;
		memset(check, false, sizeof(check));
		scanf("%d %d %d", &L, &R, &C);
		if (L == 0 && R == 0 && C == 0) break;
		for (int k = 0; k < L; k++) {
			for (int i = 0; i < R; i++) {
				scanf("%s", &map[k][i]);
				for (int j = 0; j < C; j++) {
					if(map[k][i][j]=='S') 
						start = { k,i,j,0 };
				}
			}
		}
		bfs(start);
		if (ans != 0) printf("Escaped in %d minute(s).\n", ans);
		else printf("Trapped!\n");

	}
	return 0;
}





© 2020. by Andyworkingholiday

Powered by aiden