POJ 2251 Dungeon Master （非三维bfs）

  1 #include<iostream>  
  2 #include<cstring>   //使用memset必须加此头文件
  3 #include<stdio.h>　 //使用printf必须加此头文件
  4 #include<queue>
  5 
  6 using namespace std;
  7 
  8 int L, R, C;
  9 int minute = 0;
 10 char maze[1000][1000];
 11 int vis[1000][1000];
 12 int dx[] = { 1,-1,0,0 };    //南北方向
 13 int dy[] = { 0,0,1,-1 };    //东西方向
 14 
 15 struct node
 16 {
 17     int x, y;
 18     int step;
 19 }s;
 20 
 21 void bfs(int x, int y)
 22 {
 23     s.x = x;
 24     s.y = y;
 25     s.step = 0;
 26     vis[x][y] = 1;
 27     queue<node> Q;
 28     Q.push(s);
 29 
 30     node t;
 31     while (!Q.empty())
 32     {
 33         t = Q.front();
 34         Q.pop();
 35 
 36         if (maze[t.x][t.y] == ‘E‘)
 37         {
 38             printf("Escaped in %d minute(s).\n", t.step);
 39             return;
 40         }
 41 
 42         // k表示此坐标所在的层数，因为如果只是往东西南北方向走的话，只能在同一层
 43         int k = t.x / R + 1;
 44 
 45         for (int i = 0; i < 4; ++i)
 46         {
 47             int xx = t.x + dx[i];
 48             int yy = t.y + dy[i];
 49 
 50             //注意同一层中的坐标判断条件
 51             if ((xx >= ((k - 1)*R)) && (xx < (k*R)) && yy >= 0 & yy < C && maze[xx][yy] != ‘#‘ && !vis[xx][yy])
 52             {
 53                 vis[xx][yy] = 1;
 54                 s.x = xx;
 55                 s.y = yy;
 56                 s.step = t.step + 1;
 57                 Q.push(s);
 58             }
 59         }
 60 
 61         //跳入下一层
 62         int x1 = t.x + R;
 63         int y1 = t.y;
 64         if (x1 < L*R && maze[x1][y1] != ‘#‘ && !vis[x1][y1])
 65         {
 66             vis[x1][y1] = 1;
 67             s.x = x1;
 68             s.y = y1;
 69             s.step = t.step + 1;
 70             Q.push(s);
 71         }
 72 
 73         //跳入上一层
 74         int x2 = t.x - R;
 75         int y2 = t.y;
 76         if (x2 >= 0 && maze[x2][y2] != ‘#‘ && !vis[x2][y2])
 77         {
 78             vis[x2][y2] = 1;
 79             s.x = x2;
 80             s.y = y2;
 81             s.step = t.step + 1;
 82             Q.push(s);
 83         }
 84     }
 85 
 86     cout << "Trapped!" << endl;
 87 
 88 }
 89 
 90 int main()
 91 {
 92     int start_x, start_y;    //记录起点坐标
 93     while (cin >> L >> R >> C)
 94     {
 95         if (L == 0 && R == 0 && C == 0)
 96             break;
 97 
 98         for (int i = 0; i < L*R; ++i)
 99             for (int j = 0; j < C; ++j)
100             {
101                 cin >> maze[i][j];    //迷宫下标从0开始存储
102                 if (maze[i][j] == ‘S‘)
103                 {
104                     start_x = i;
105                     start_y = j;
106                 }
107             }
108 
109         memset(vis, 0, sizeof(vis));
110         bfs(start_x, start_y);
111 
112     }
113     return 0;
114 }