[UVa] 532 - Dungeon Master

With this, I get inside the first 1000 coders on UVa. :)

Submission details:

Submission no: 9461491
Problem no: 532 
Problem title: Dungeon Master
Status: Accepted
Language: C++
Runtime: 0.012
Date of submission: 2011-11-11
Time of submission: 11:12:39

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define INF 9999999
using namespace std;

typedef struct xp
{
    int l, x, y;
} cord;

bool color[100][100][100];
int d[100][100][100];
char inp[100][100][100];

int dirs[10][4]={ {-1,0,0}, {1,0,0}, {0,-1,0}, {0,0,-1}, {0,0,1}, {0,1,0} };

int bfs(cord S, cord E, cord M)
{
    int i, j, k;

    for (i=0 ; i<=M.l+1 ; i++)
    {
        for (j=0 ; j<=M.x+1 ; j++)
        {
            for (k=0 ; k<=M.y+1 ; k++)
            {
                color[i][j][k]=false;
                d[i][j][k]=INF;
            }
        }
    }
    color[S.l][S.x][S.y]=true;
    d[S.l][S.x][S.y]=0;

    cord u, temp;

    queue<cord> q;
    q.push(S);
    while (!q.empty())
    {
        u = q.front();
        q.pop();

        for (i=0 ; i<6 ; i++)
        {
            temp.l = u.l+dirs[i][0];
            temp.x = u.x+dirs[i][1];
            temp.y = u.y+dirs[i][2];

            if (!color[temp.l][temp.x][temp.y] && inp[temp.l][temp.x][temp.y]!='#')
            {
                if (temp.l<1||temp.l>M.l||temp.x<1||temp.x>M.x||temp.y<1||temp.y>M.y)
                    continue;
                color[temp.l][temp.x][temp.y]=true;
                d[temp.l][temp.x][temp.y]=d[u.l][u.x][u.y]+1;
                if (i==E.l && j==E.x && k==E.y) return d[temp.l][temp.x][temp.y];
                    q.push(temp);
            }
        }
    }

    return d[E.l][E.x][E.y];
}


int main()
{
    int l, w, h, i, j, k, res;
    cord S, E, M;
    while (scanf("%d %d %d",&l,&h,&w)==3 && l&&h&&w)
    {
        getchar();

        M.l = l;
        M.x = h;
        M.y = w;

        for (i=1 ; i<=l ; i++)
        {
            for (j=1 ; j<=h ; j++)
            {
                gets(&inp[i][j][1]);
                for (k=1 ; k<=w ; k++)
                {
                    if (inp[i][j][k]=='S')
                    {
                        S.l = i;
                        S.x = j;
                        S.y = k;
                    }
                    if (inp[i][j][k]=='E')
                    {
                        E.l = i;
                        E.x = j;
                        E.y = k;
                    }
                }
            }
            gets(&inp[i][j][1]);
        }

        res = bfs(S,E,M);

        if (res==INF)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",res);
    }
    return 0;
}