top1编程
← 返回题目
题解

最短路径

2 条题解

  • 0
    @ 2026-7-29 2:09:13
    #include<bits/stdc++.h>
    using namespace std;
    int  a[155][155];
    int b[25000][5],t=1,w=1,b1,b2,e1,e2;
    int fx[5]={0,0,1,0,-1};
    int fy[5]={0,1,0,-1,0};
    void dy(int k){//传递尾巴的值
    	if(b[k][3]!=0){//有父节点
    		dy(b[k][3]);//继续找当前点有没有父节点
    	}
    	cout<<"("<<b[k][1]<<","<<b[k][2]<<")";
    	if(k!=w){//不是最后一个输出箭头
    		cout<<"->";
    	}
    }
    int main()
    {
    	int n,m;
    	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;
    	b[1][1]=b1;
    	b[1][2]=b2;
    	b[1][3]=0;//第一个点没有父节点
    	while(t<=w){
    		for(int i=1;i<=4;i++){
    			int tx=b[t][1]+fx[i];
    			int ty=b[t][2]+fy[i];
    			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){//可以走
    				w++;
    				a[tx][ty]=1;//标记走过
    				b[w][1]=tx;
    				b[w][2]=ty;
    				b[w][3]=t;//记录每个父节点
    				if(tx==e1&&ty==e2){//找到终点
    					dy(w);//通过递归从前往后打印
    					return 0;
    				}
    			}
    		}
    		t++;
    	}
    	cout<<"no way";
    }
    
    • 0
      @ 2026-7-29 1:48:50
      #include<bits/stdc++.h>
      using namespace std;
      int  a[155][155];
      int b[25000][5],t=1,w=1,b1,b2,e1,e2;
      int fx[5]={0,0,1,0,-1};
      int fy[5]={0,1,0,-1,0};
      void dy(int k){//传递尾巴的值
      	if(b[k][3]!=0){//有父节点
      		dy(b[k][3]);//继续找当前点有没有父节点
      	}
      	cout<<"("<<b[k][1]<<","<<b[k][2]<<")";
      	if(k!=w){//不是最后一个输出箭头
      		cout<<"->";
      	}
      }
      int main()
      {
      	int n,m;
      	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;
      	b[1][1]=b1;
      	b[1][2]=b2;
      	b[1][3]=0;//第一个点没有父节点
      	while(t<=w){
      		for(int i=1;i<=4;i++){
      			int tx=b[t][1]+fx[i];
      			int ty=b[t][2]+fy[i];
      			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){//可以走
      				w++;
      				a[tx][ty]=1;//标记走过
      				b[w][1]=tx;
      				b[w][2]=ty;
      				b[w][3]=t;//记录每个父节点
      				if(tx==e1&&ty==e2){//找到终点
      					dy(w);//通过递归从前往后打印
      					return 0;
      				}
      			}
      		}
      		t++;
      	}
      	cout<<"no way";
      }
      
      • 1