题解
迷宫的最短路径
2 条题解
-
0
#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
#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