top1编程
← 返回题目
题解

【提高】走出迷宫的最短路径

1 条题解

  • 0
    @ 2026-7-28 22:09:23
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,a[155][155],b1,b2,e1,e2,t=1,w=1,d[22600][4];
    int fx[10]={0,0,1,0,-1};
    int fy[10]={0,1,0,-1,0};
    void dy(int k){
    	if(d[k][3]!=0){//有父节点
    		dy(d[k][3]);//递归,回到第一个点
    	}
    	cout<<"("<<d[k][1]<<","<<d[k][2]<<")";
    	if(k!=w){//不是最后一个输出箭头
    		cout<<"->";
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>a[i][j];//读入迷宫状态
    		}
    	}
    	cin>>b1>>b2>>e1>>e2;//输入起点和终点
    	d[1][1]=b1;
    	d[1][2]=b2;
    	d[1][3]=0;//第一个点没有父节点
    	while(t<=w){//可以探索
    		//更新方向
    		for(int i=1;i<=4;i++){
    			int tx=d[t][1]+fx[i];
    			int ty=d[t][2]+fy[i];
    			//在范围内且能走
    			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){
    				w++;
    				a[tx][ty]=1;//标记走过
    				d[w][1]=tx;
    				d[w][2]=ty;
    				d[w][3]=t;//更新当前点的父节点
    				if(tx==e1&&ty==e2){//到终点
    					dy(w);//通过最后一个点找前驱点并打印
    					return 0;
    				}
    			}
    		}
    		t++;
    	}
    	cout<<"no way";
    	return 0;
    }
    
    • 1