[POJ 2251] Dungeon Master

谁借莪１个温暖的怀抱￠ 2022-01-12 06:07 168阅读 0赞

题目链接：http://poj.org/problem?id=2251

注意：细心细心再细心！！

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<queue>
     5 using namespace std;
     6 
     7 const int maxn = 35;
     8 int L,R,C;
     9 bool vis[maxn][maxn][maxn];
    10 char maze[maxn][maxn][maxn];
    11 int go[6][3] = {
        0,0,1,0,0,-1,0,1,0,0,-1,0,1,0,0,-1,0,0};
    12 struct node
    13 {
    14     int x,y,z;
    15     int count;
    16 }now,nex;
    17 
    18 bool IsOk(node s)
    19 {
    20     return (s.x>=0&&s.x<L&&s.y>=0&&s.y<R&&s.z>=0&&s.z<C&&!vis[s.x][s.y][s.z]&&maze[s.x][s.y][s.z]!='#');
    21 }
    22 
    23 int bfs()
    24 {
    25     queue<node> Q;
    26     vis[now.x][now.y][now.z]=1;
    27     Q.push(now);
    28     while(!Q.empty())
    29     {
    30         now = Q.front();
    31         Q.pop();
    32         if(maze[now.x][now.y][now.z]=='E')
    33             return now.count;
    34         for(int i=0;i<6;i++)
    35         {
    36             nex.x = now.x + go[i][0];
    37             nex.y = now.y + go[i][1];
    38             nex.z = now.z + go[i][2];
    39             if(IsOk(nex))
    40             {
    41                 vis[nex.x][nex.y][nex.z]=1;
    42                 nex.count = now.count + 1;
    43                 Q.push(nex);
    44             }
    45         }
    46     }
    47     return 0;
    48 }
    49 
    50 int main()
    51 {
    52     while(~scanf("%d%d%d",&L,&R,&C)&&(L||R||C))
    53     {
    54         for(int i=0;i<L;i++)
    55         {
    56             for(int j=0;j<R;j++)
    57                 scanf("%s",maze[i][j]);
    58             getchar();
    59         }
    60         int flag = 0;
    61         for(int i=0;i<L;i++)
    62         {
    63             for(int j=0;j<R;j++)
    64             {
    65                 for(int k=0;k<C;k++)
    66                     if(maze[i][j][k]=='S')
    67                     {
    68                         now.x=i;now.y=j;now.z=k;
    69                         now.count=0;
    70                         flag = 1;
    71                         break;
    72                     }
    73                 if(flag)
    74                     break;    
    75             }
    76             if(flag)
    77                 break;
    78         }
    79         memset(vis,0,sizeof(vis));
    80         int ans = bfs();
    81         if(ans)
    82             printf("Escaped in %d minute(s).\n",ans);
    83         else
    84             printf("Trapped!\n");
    85     }
    86     return 0;
    87 }

复习一遍，代码和上面的稍有不同：

1 #include<cstdio>
     2 #include<cstring>
     3 #include<queue>
     4 using namespace std;
     5 
     6 const int maxn = 30;
     7 char maze[maxn][maxn][maxn];
     8 bool vis[maxn][maxn][maxn];
     9 int go[6][3] = {
        0,0,1,0,0,-1,1,0,0,-1,0,0,0,-1,0,0,1,0};
    10 int l,r,c;
    11 int sx,sy,sz;
    12 struct Point
    13 {
    14     int x,y,z;
    15     int cnt;
    16 }now,nex;
    17 
    18 bool IsOk(Point s)
    19 {
    20     if(s.x<0||s.x>=l||s.y<0||s.y>=r||s.z<0||s.z>=c)
    21         return 0;
    22     else if(maze[s.x][s.y][s.z] == '#')
    23         return 0;
    24     else if(vis[s.x][s.y][s.z])
    25         return 0;
    26     else
    27         return 1;
    28 }
    29 int BFS()
    30 {
    31     now.x = sx;now.y = sy;now.z = sz;
    32     now.cnt = 0;
    33     vis[sx][sy][sz] = 1;
    34     queue<Point> q;
    35     q.push(now);
    36     while(!q.empty())
    37     {
    38         now = q.front();
    39         q.pop();
    40         if(maze[now.x][now.y][now.z] == 'E')
    41         {
    42             return now.cnt;
    43         }
    44         for(int i=0;i<6;i++)
    45         {
    46             nex.x = now.x + go[i][0];
    47             nex.y = now.y + go[i][1];
    48             nex.z = now.z + go[i][2];
    49             if(IsOk(nex))
    50             {
    51                 vis[nex.x][nex.y][nex.z] = 1;
    52                 nex.cnt = now.cnt + 1;
    53                 q.push(nex);
    54             }
    55         }
    56     }
    57     return -1;
    58 }
    59 
    60 int main()
    61 {
    62     while(~scanf("%d%d%d",&l,&r,&c)&&(l||r||c))
    63     {
    64         for(int i=0;i<l;i++)
    65         {
    66             for(int j=0;j<r;j++)
    67                 scanf("%s",maze[i][j]);
    68             getchar();
    69         }
    70         bool flag = 0;
    71         for(int i=0;i<l;i++)
    72         {
    73             for(int j=0;j<r;j++)
    74             {
    75                 for(int k=0;k<c;k++)
    76                 {
    77                     if(maze[i][j][k] == 'S')
    78                     {
    79                         sx = i;sy = j;sz = k;
    80                         flag = 1;
    81                         break;
    82                     }
    83                 }
    84                 if(flag)
    85                     break;
    86             }
    87             if(flag)
    88                 break;
    89         }
    90         memset(vis,0,sizeof(vis));
    91         int ans = BFS();
    92         if(ans==-1)
    93             printf("Trapped!\n");
    94         else
    95             printf("Escaped in %d minute(s).\n",ans);
    96     }
    97     return 0;
    98 }

转载于:https://www.cnblogs.com/youpeng/p/10245443.html