02.28 王琼老师第一次通过二叉树的遍历给大家引荐了深度优先搜索。
6行8列的迷宫，计算从(0,0)到(5,7)的路径
0 0 1 0 0 0 0 0
1 0 1 0 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 0 1 0 1
1 0 1 1 0 1 1 1
1 0 0 0 0 0 0 0
请各位同学编程，实现最短路径并打印
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include <iostream>
using namespace std;
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<cmath>
#include<queue>
#define EPS 1e-6
#define MAX 1010
int ans,mp[MAX][MAX],vis[MAX][MAX],xi[MAX],yi[MAX],cnt=0;
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
struct node{
int x,y,step;
};
node pre[MAX][MAX];
bool check(int px,int py){
if(px<0||py<0||px>=6||py>=8||mp[px][py]==1) return false;
return true;
}
void init(){
ans=0;
memset(vis,0,sizeof(vis));
}
void bfs(int px,int py){
queue <node> Q;
Q.push(node{px,py,0});
vis[px][py]=1;
while(!Q.empty()){
node t=Q.front();
Q.pop();
if(t.x==5&&t.y==7){
ans=t.step;
break;
}
for(int i=0;i<4;i++){
int nx=t.x+dx[i];
int ny=t.y+dy[i];
if(check(nx,ny)&&!vis[nx][ny]){
Q.push(node{nx,ny,t.step+1});
vis[nx][ny]=1;
pre[nx][ny]=t;
}
}
}
}
void print(node cur){
if(cur.x==0&&cur.y==0){
cout<<"(0, 0)"<<endl;
return;
}
print(pre[cur.x][cur.y]);
cout<<"("<<cur.x<<", "<<cur.y<<")"<<endl;
}
int main(){
cout<<"迷宫:"<<endl;
for(int i=0;i<6;i++){
for(int j=0;j<8;j++){
cin>>mp[i][j];
}
}
bfs(0,0);
cout<<"最短路径如下："<<endl;
print(node{5,7,ans});
cout<<"最短路径步数:"<<endl;
cout<<ans<<"步";
return 0;
}
