runtah

UVa 532 Dungeon Master

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! ");
 else
 printf("Escaped in %d minute(s). ",res);
 }
 return 0;
}

Go to link download