Week 5 - BFS

<180324>

Week5 - BFS

[6593] 상범빌딩 (http://boj.kr/6593)

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int L, R, C; };
 
int L, R, C;
int dl[]={1, -1, 0, 0, 0, 0};
int dr[]={0, 0, 1, -1, 0, 0};
int dc[]={0, 0, 0, 0, 1, -1};
 
bool safe(int l, int r, int c)
{
    return (0 <= l && l < 30) && (0 <= r && r < 30) && (0 <= c && c < 30);
}
 
int main()
{
    while(1) {
 
        scanf("%d%d%d", &L, &R, &C);
 
        if(!L && !R && !C) break;
 
        P s, e;
        char g[31][31][31];
        for(int l=0; l<L; l++) {
            for(int r=0; r<R; r++) 
                scanf("%s", g[l][r]);
            for(int r=0; r<R; r++) {
                for(int c=0; c<C; c++) {
                    if(g[l][r][c] == 'S')
                        s = (P){l, r, c};
                    if(g[l][r][c] == 'E') {
                        g[l][r][c] = '.';
                        e = (P){l, r, c};
                    }
                }
            }
        }
 
        queue<P> q;
        q.push(s);
        
        int visited[31][31][31]={0};
        visited[s.L][s.R][s.C] = 1;
 
        while(!q.empty()) {
            int curL = q.front().L;
            int curR = q.front().R;
            int curC = q.front().C; q.pop();
            
            if(curL == e.L && curR == e.R && curC == e.C) break;
 
            for(int k=0; k<6; k++) {
                int nL = curL+dl[k];
                int nR = curR+dr[k];
                int nC = curC+dc[k];
                if(safe(nL, nR, nC) && g[nL][nR][nC]=='.' && !visited[nL][nR][nC]) {
                    visited[nL][nR][nC] = visited[curL][curR][curC]+1;
                    q.push((P){nL, nR, nC});
                }
            }
        }
        
        int ans = visited[e.L][e.R][e.C];
        if(!ans) puts("Trapped!");
        else printf("Escaped in %d minute(s).\n", ans-1);
    }
}

>> 3차원을 확장되었을 뿐, 이전 문제들과 동일하다.

>> 36번줄에 대해 처리를 안하면 답이 안나온다...

[5014] 스타트링크 (http://boj.kr/5014)

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int F, S, G, U, D;
int visited[1000001];
 
int main()
{
    scanf("%d%d%d%d%d", &F, &S, &G, &U, &D);
 
    queue<int> q;
    q.push(S);
    visited[S] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        
        if(cur == G) break;
 
        int next = cur+U;
        if(next < 1000001 && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
 
        next = cur-D;
        if(0 <= next && !visited[next]) { q.push(next); visited[next] = visited[cur]+1; }
    }
    
    if(!visited[G]) puts("use the stairs");
    else printf("%d\n", visited[G]-1);
}

[]