首页 > 学院 > 开发设计 > 正文

HDU 2102 A 计划(bfs)

2019-11-08 03:22:59
字体:
来源:转载
供稿:网友

刚开始没注意到起点已经给定(0,0,0),还自己通过S去找到起点的坐标;

#include<cstdio>#include<queue>#include<cstring>using namespace std;const int maxn=10+2;struct node{	int x,y,z;	node(int x=0,int y=0,int z=0):x(x),y(y),z(z){}}ne;char g[maxn][maxn][maxn];int d[maxn][maxn][maxn];int N,M,T;int dir[][2]={{1,0},{-1,0},{0,-1},{0,1}};  //上下左右 bool isValid(node &nd){	return nd.x>=0&&nd.x<N && nd.y>=0&&nd.y<M;}void bfs(){	memset(d,0,sizeof(d));	queue<node>q;	q.push(node(0,0,0));	while(!q.empty()){		node u=q.front();		q.pop();		if(u.x==ne.x && u.y==ne.y && u.z==ne.z){			if(d[u.x][u.y][u.z]>T){			PRintf("NO/n");return ; 		}			printf("YES/n");			return ;		}		for(int i=0;i<4;i++){				node v=node(dir[i][0]+u.x,dir[i][1]+u.y,u.z);				if(isValid(v) && !d[v.x][v.y][v.z] && g[v.x][v.y][v.z]!='*')				{				if(g[v.x][v.y][v.z]!='#')q.push(v);        //如果是传输机不加入队列 				d[v.x][v.y][v.z]=d[u.x][u.y][u.z]+1;								if(g[v.x][v.y][v.z]=='#'){				int t;				if(u.z==0)t=1;				else t=0;				node v2=node(v.x,v.y,t);								if(g[v2.x][v2.y][v2.z]!='*' && g[v2.x][v2.y][v2.z]!='#' && !d[v2.x][v2.y][v2.z]){					q.push(v2);					d[v2.x][v2.y][v2.z]=d[v.x][v.y][v.z];				}			}		  }		}	}	printf("NO/n");}int main(){	int C;	scanf("%d",&C);	while(C--){		scanf("%d%d%d",&N,&M,&T);		getchar();	for(int k=0;k<2;k++){		for(int i=0;i<N;i++){			for(int j=0;j<M;j++){			scanf("%c",&g[i][j][k]);			if(g[i][j][k]=='P')ne.x=i,ne.y=j,ne.z=k;			}			getchar();		}		if(k==0)getchar();	}		bfs();	}	return 0;} 

在网上找了几组测试数据,可以试下:

6  5 5 14S*#*..#........****....#...*.P#.*..***.....*.*.#..5 5 13S*#*..#........****....#...*.P#.*..***.....*.*.#..5 5 13S*#*..#........****....#...*.P#.*..***.....*.*.##.5 5 8S*#*#.#**......*****...#...*.P#.*..***.....*.*.##.1 4 10.#.#*.#P1 4 2.#.#*.#P

格式自己再调下,复制上来有点不对


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表