题解
【提高】走出迷宫的最短路径
1 条题解
-
0
#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