[문제풀이] 6593번: 상범 빌딩

[문제풀이] 상범 빌딩

https://www.acmicpc.net/problem/6593

문제유형

BFS

Solution

#include <stdio.h>
#define MAX 32
#define CIR (32*32*32)
int L, R, C;    //던전 층수, 행 렬,
char map[MAX][MAX][MAX];
char chk[MAX][MAX][MAX];
typedef struct st
{
    int count;
    int x, y, z;
}POS;
POS start;
POS end;
POS q[CIR];
 
void init()
{
    int i, j, k;
    for (i = 0; i < MAX; i++)
    {
        for (j = 0; j < MAX; j++)
        {
            for (k = 0; k < MAX; k++)
            {
                map[i][j][k] = 0;
                chk[i][j][k] = 0;
            }
        }
    }
    start.x = 0; start.y = 0; start.z = 0; start.count = 0;
    end.x = 0; end.y = 0; end.z = 0; end.count = 0;
}
 
void inputData()
{
    int i, j, l;
    scanf("%d %d %d", &L, &R, &C);
    for (l = 0; l < L; l++)
    {
        for (i = 0; i < R; i++)
        {
            for (j = 0; j < C; j++)
            {
                char ch = 0;
                scanf(" %c", &ch);
                map[l][i][j] = ch;
                if (ch == 'S')
                {
                    start.x = j;
                    start.y = i;
                    start.z = l;
                    start.count = 0;
                    chk[l][i][j] = 1;
                }
                else if (ch == 'E')
                {
                    end.x = j;
                    end.y = i;
                    end.z = l;
                }
            }
        }
    }
}
 
int bfs()
{
    int k;
    int dx[6] = { -1, 0, 1, 0, 0, 0};
    int dy[6] = { 0, -1, 0, 1, 0, 0};
    int dz[6] = { 0, 0, 0, 0, -1, 1};
    POS ndata, tdata;
    int wp = 0, rp = 0;
 
    q[wp++] = start;
    wp %= CIR;
    //printf("[push] %d %d %d\n", start.x, start.y, start.z);
 
    while (wp != rp)
    {
        tdata = q[rp++];
        rp %= CIR;
 
        for (k = 0; k < 6; k++)
        {
            ndata.x = tdata.x + dx[k];
            ndata.y = tdata.y + dy[k];
            ndata.z = tdata.z + dz[k];
            ndata.count = tdata.count + 1;
 
            if (ndata.z < 0 || ndata.y < 0 || ndata.x < 0) continue;
            if (ndata.z >= L || ndata.y >= R || ndata.x >= C) continue;
            if (map[ndata.z][ndata.y][ndata.x] == '#') continue;
            if (chk[ndata.z][ndata.y][ndata.x]) continue;
 
            if (ndata.z == end.z && ndata.y == end.y && ndata.x == end.x)
            {
                return ndata.count;
            }
 
            chk[ndata.z][ndata.y][ndata.x] = 1;
 
            q[wp++] = ndata;
            wp %= CIR;
        }
    }
    return 0;
}
 
void solve()
{
    int ret = 0;
    if (ret = bfs())
    {
        printf("Escaped in %d minute(s).\n", ret);
    }
    else
    {
        printf("Trapped!\n");
    }
}
 
int main()
{
    for (;;)
    {
        init();
        inputData();
        if (L == 0 && R == 0 && C == 0) break;
        solve();
    }
 
    return 0;
}