HDU 2102 A 计划（bfs）

清疚 2024-02-17 19:10 29阅读 0赞

刚开始没注意到起点已经给定（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 14  
S\*\#\*.  
.\#...  
.....  
\*\*\*\*.  
...\#.  
  
  
..\*.P  
\#.\*..  
\*\*\*..  
...\*.  
\*.\#..  
5 5 13  
S\*\#\*.  
.\#...  
.....  
\*\*\*\*.  
...\#.  
  
  
..\*.P  
\#.\*..  
\*\*\*..  
...\*.  
\*.\#..  
5 5 13  
S\*\#\*.  
.\#...  
.....  
\*\*\*\*.  
...\#.  
  
  
..\*.P  
\#.\*..  
\*\*\*..  
...\*.  
\*.\#\#.  
5 5 8  
S\*\#\*\#  
.\#\*\*.  
.....  
\*\*\*\*\*  
...\#.  
  
  
..\*.P  
\#.\*..  
\*\*\*..  
...\*.  
\*.\#\#.  
1 4 10  
.\#.\#  
  
  
\*.\#P  
1 4 2  
.\#.\#  
  
  
\*.\#P

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