BFS（广度优先搜索）

bzlx1717 / 2023-05-18 / 原文

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100][100],v[100][100];// a为地图，v为记录是否访问
struct point{
int x;
int y;
int step;
};// 建立访问节点的结构体
queue<point> r;// 创建队列
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};// 创建遍历方向
int main()
{ int n,m,startx,starty,p,q;
　　cin>>n>>m;// n，m为地图长宽
　　for(int i=1;i<=n;i++)
　　　　for(int j=1;j<=m;j++)
　　　　　　cin>>a[i][j];// 填充地图
　　cin>>startx>>starty>>p>>q;
　　point start;
　　start.x = startx;
　　start.y = starty;
　　start.step = 0;// 建立初始点
　　r.push(start);// 入队
　　v[startx][starty] = 1;// 设置该点为已访问
　　int flag = 0;// 判断是否有解
　　while(!r.empty()){// 如果队列不为空
　　　　int x=r.front().x,y = r.front().y;// 队首节点
　　　　if(x==p && y==q){
　　　　　　flag = 1;
　　　　　　cout<<r.front().step;
　　　　　　break;
　　　　}
　　　　for(int k=0;k<=3;k++){// 遍历4个方向
　　　　　　int tx,ty;
　　　　　　tx = x+dx[k];
　　　　　　ty = y+dy[k];
　　　　　　if(a[tx][ty]==1 && v[tx][ty]==0)// 下一个访问点为无障碍并且未访问{
　　　　　　point temp;
　　　　　　temp.x = tx;
　　　　　　temp.y = ty;
　　　　　　temp.step = r.front().step + 1;
　　　　　　r.push(temp);// 入队
　　　　　　v[tx][ty] = 1;// 设置为已访问
　　　　　　}
　　　　}
　　r.pop();// 出队
　　}
if(flag == 0){
　　cout<<"no answer!"<<endl;
}
return 0;
}