상범 빌딩 (feat. 백준, 6593번)

상범 빌딩
https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
char arr[51][51][51];
int L, R, C, dx[4], dy[4], sl, sr, sc, el, er, ec;
bool visit[51][51][51];
int bfs(register int l, register int r, register int c){
    memset(visit, false, sizeof(visit));
    register int time = -1, t, nl;
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(l, r, c, 0));
    visit[l][r][c] = true;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        l = get<0>(p), r = get<1>(p), c = get<2>(p), t = get<3>(p);
        if(l == el && r == er && c == ec){
            time = t;
            break;
        }
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = r + dx[d], ny = c + dy[d];
            if(1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[l][nx][ny] && arr[l][nx][ny] != '#')
                visit[l][nx][ny] = true, q.push(make_tuple(l, nx, ny, t + 1));
        }
        if((nl = l - 1) >= 1 && !visit[nl][r][c] && arr[nl][r][c] != '#')
            visit[nl][r][c] = true, q.push(make_tuple(nl, r, c, t + 1));
        if((nl = l + 1) <= L && !visit[nl][r][c] && arr[nl][r][c] != '#')
            visit[nl][r][c] = true, q.push(make_tuple(nl, r, c, t + 1));
    }
    return time;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    while(1){
        cin >> L >> R >> C;
        if(L == 0 && R == 0 && C == 0)
            break;
        for(register int l = 1, r, c; l <= L; ++l)
            for(r = 1; r <= R; ++r)
                for(c = 1; c <= C; ++c){
                    cin >> arr[l][r][c];
                    if(arr[l][r][c] == 'S')
                        sl = l, sr = r, sc = c;
                    else if(arr[l][r][c] == 'E')
                        el = l, er = r, ec = c;
                }
        register int ans = bfs(sl, sr, sc);
        if(ans == -1)
            cout << "Trapped!\n";
        else
            cout << "Escaped in " << ans << " minute(s).\n";
    }
	return 0;
}
// *&)*@*

 

반응형

익숙한 상,하,좌,우 의 bfs에서 위와 아래 (up, down) 도 고려해야 하는 bfs 문제입니다.