POJ2251 Dungeon Master(BFS)

题意：

要逃出地牢，地牢是三维的，有上下层之分

要点：

就是将原本二维的BFS转换为三维的就可以了，求最短距离，这种BFS我还是可以做的

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
char map[35][35][35];
bool visit[35][35][35];
int l, r, c;
int d[6][3] = { { 1,0,0 },{ -1,0,0 },{ 0,1,0 },{ 0,-1,0 },{ 0,0,1 },{ 0,0,-1 } };//三维的改变数组
struct node
{int x, y, z;int count;
};bool judge(int x, int y, int z)//限定的条件判断
{if (x >= 0 && x < l&&y >= 0 && y < r&&z >= 0 && z < c&&visit[x][y][z]&&map[x][y][z]!='#')return true;return false;
}int bfs(int x, int y, int z)
{queue<node> que;node u;u.x = x; u.y = y; u.z = z;u.count = 0;que.push(u);visit[x][y][z] = false;while (!que.empty()){node temp=que.front();if (map[temp.x][temp.y][temp.z] == 'E')return temp.count;que.pop();for (int i = 0; i < 6; i++){node v;v.x = temp.x + d[i][0];v.y = temp.y + d[i][1];v.z = temp.z + d[i][2];if (judge(v.x,v.y,v.z)){visit[v.x][v.y][v.z] = false;v.count = temp.count+1;que.push(v);}}}return 0;//如果出不来就输出0
}int main()
{int i, j, k,sx,sy,sz;while (~scanf("%d%d%d", &l, &r, &c),l+r+c){memset(map, 0, sizeof(map));memset(visit, true, sizeof(visit));for (i = 0; i < l; i++)for (j = 0; j < r; j++){scanf("%s", map[i][j]);for (k = 0; k < c; k++){if (map[i][j][k] == 'S') { sx = i; sy = j; sz = k; }}}int step=bfs(sx, sy, sz);if (step)printf("Escaped in %d minute(s).\n", step);elseprintf("Trapped!\n");}return 0;
}