HDU - 2102 A计划 (BFS) [kuangbin带你飞]专题二

       思路：接BFS判断能否在限制时间内到达公主的位置，注意如果骑士进入传送机就会被立即传送到另一层，不会能再向四周移动了，例如第一层的位置(x, y, 1)是传送机，第二层(x, y, 2)也是传送机，这种情况骑士会一直被传上传下。

   AC代码： 0ms

#include<cstdio>#include<cmath>#include<cstring>#include<queue>using namespace std;const int maxn = 15;char G[2][maxn][maxn];int d[2][maxn][maxn];int n, m, Limit;const int dx[] = {0,0,-1,1};const int dy[] = {1,-1,0,0};const int dz[] = {1,-1};struct point{	int x, y, z;	point(){	}	point(int x, int y, int z):x(x), y(y), z(z){	}};bool bfs() {	memset(d, -1, sizeof(d));	d[0][0][0] = 0;	queue<point>q;	q.push(point(0, 0, 0));	while(!q.empty()) {		point p = q.front(); 		q.pop();		int x = p.x, y = p.y, z = p.z;		if(d[z][x][y] > Limit) return false;		if(G[z][x][y] == 'P') return true;				int flag = 0;		if(G[z][x][y] == '#') { //传送机 			flag = 1;			for(int i = 0; i < 2; ++i) {				int pz = z + dz[i];				if(pz < 0 || pz >= 2) continue;				if(G[pz][x][y] == '*' || d[pz][x][y] != -1) continue;				d[pz][x][y] = d[z][x][y];				q.push(point(x, y, pz));			}		}		if(flag) continue;				for(int i = 0; i < 4; ++i) {			int px = x + dx[i], py = y + dy[i];			if(px < 0 || py < 0 || px >= n || py >= m) continue;			if(d[z][px][py] != -1 || G[z][px][py] == '*') continue;			d[z][px][py] = d[z][x][y] + 1;			q.push(point(px, py, z));		}	}	return false;}int main() {	int T;	scanf("%d", &T);	while(T--) {		scanf("%d%d%d", &n, &m, &Limit);		for(int i = 0; i < 2; ++i) {			for(int j = 0; j < n; ++j) scanf("%s", G[i][j]);		}		if(bfs()) PRintf("YES/n");		else printf("NO/n");	}	return 0;}如有不当之处欢迎指出！