Saturday, 14 January 2017

UVa 532 - Dungeon Master

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w,i,j,k;
    while(1)
    {
        cin>>w>>r>>c;
        if(w==0&&r==0&&c==0)
            break;
        int stx,sty,stz,enx,eny,enz;
        memset(graph,0,sizeof(graph));
        for(i=0;i<w;i++)
        {
            for(j=0;j<r;j++)
            {
                for(k=0;k<c;k++)
                {
                    char c;
                    cin>>c;
                    if(c=='S')
                    {
                        stx=i;
                        sty=j;
                        stz=k;
                        graph[i][j][k]=1;
                        continue;
                    }
                    if(c=='E')
                    {
                        enx=i;
                        eny=j;
                        enz=k;
                        graph[i][j][k]=1;
                    }
                    if(c=='.')
                        graph[i][j][k]=1;
                    if(c=='#')
                        graph[i][j][k]=0;
                }
            }
        }
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        visited[stx][sty][stz]=true;
        level[stx][sty][stz]=0;
        q.push(stx);
        q.push(sty);
        q.push(stz);
        int ans;
        bool flag=0;
        while(!q.empty())
        {
            int f1,f2,f3;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            f3=q.front();
            q.pop();
            for(int in=0;in<6;in++)
            {
                int v1,v2,v3;
                v1=f1+x[in];
                v2=f2+y[in];
                v3=f3+z[in];
                if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
                {
                    {
                        level[v1][v2][v3]=level[f1][f2][f3]+1;
                        //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                        if(v1==enx&&v2==eny&&v3==enz)
                        {
                            flag=1;
                            ans=level[v1][v2][v3];
                        }
                        q.push(v1);
                        q.push(v2);
                        q.push(v3);
                        visited[v1][v2][v3]=true;
                    }
                }
            }
        }
        if(flag)
        {
            if(ans<2)
            {
                cout<<"Escaped in "<<ans<<" minute."<<endl;
            }
            else
            {
                cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
            }
        }
        else
            cout<<"Trapped!"<<endl;
    }
    return 0;
}

No comments:

Post a Comment