1 条题解

  • 0
    @ 2025-10-10 15:48:07

    C++ :

    #include<iostream>
    #include<cstring>
    using namespace std;
    
    //初始化方向
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0}; 
    
    int map[200][200];
    
    int que[10000][3];//队列数组
    int pre[10000];//存放前驱节点的数组
    int head=0;
    int tail=1;
    	
    //递归输出路径 
    int print(int d){
    	if(pre[d]!=0){
    		print(pre[d]);
    	} 
    	
    	if(d != tail){
    		cout<<"("<<que[d][1]<<","<<que[d][2]<<")"<<"->";
    	}else{
    		cout<<"("<<que[d][1]<<","<<que[d][2]<<")"<<endl;
    	}
    	
    }
    			   
    int main(){
    	int i,j,n,m;
    	cin>>n>>m;
    	for(i = 1;i <= n;i++){
    		for(j = 1;j <= m;j++){
    			cin>>map[i][j];
    		}
    	}
    	
    	int soux,souy;//起点坐标 
    	int desx,desy;//终点坐标 
    	
    	cin>>soux>>souy;
    	cin>>desx>>desy;
    
    	bool flag=false;//假设没有路径
    	
    	map[soux][souy]=1;//经过的点设置成1,避免重复
    	//起点入队 
    	que[tail][1]=soux;
    	que[tail][2]=souy;
    	//起点没有前驱
    	pre[tail]=0; 
    	 
    	while(head!=tail){
    		head++;
    		//循环4个方向 
    		for(int i=0;i<4;i++){
    			
    			int x=que[head][1]+dx[i];
    			int y=que[head][2]+dy[i]; 
    			//设置边界 
    			if(((x>0)&&(x<=n))&&((y>0)&&(y<=m))&&map[x][y]==0){
    				tail++;
    				que[tail][1]=x;
    				que[tail][2]=y;
    				pre[tail]=head;
    				//标记该点已经走过
    				map[x][y]=1;
    				//如果扩展到了目标节点
    				if((x==desx)&&(y==desy)){
    					flag=true;//找到了路径
    					print(tail);//打印路径 
    					break; //跳出当前循环 
    				}
    			}
    			
    		}
    		//如果找到了路径 
    		if(flag==true){
    			break;//跳出最外层循环 
    		}
    	} 
    	
    	//如果没有路径 
    	if(flag==false){
    		cout<<"no way"<<endl; 
    	} 
    	 
    }				
    
    
    • 1

    信息

    ID
    422
    时间
    1000ms
    内存
    120MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者