广度优先搜索:
广度优先搜索是一步将所以相同距离的结点找到(入队),然后对队中的队头元素进行操作后出队;接着再把距离+1的所有结点入队;反复进行,直到队为空。因此广度优先搜索对于每条边权重为1的图(必须为1),搜索到某点的步数是该点到初始点最少的步数(最短路径)。广度优先搜索题的模板就是定义一个队列,然后while循环,循环条件是队列不为空
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int n,m;
int g[N][N],d[N][N]; //g是地图,d是地图上的结点距离初始点(1,1)的距离
queue<PII> q;
int dy[4]={0,1,0,-1},dx[4]={-1,0,1,0}; //技巧:上下左右移动,可以用两个数字储存,如(0,1)表示向上移动
void bfs()
{
d[1][1]=0;
q.push({1,1});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(d[x][y]==-1&&g[x][y]==0&&y>=1&&y<=m&&x>=1&&x<=n) //二维矩阵一般用横轴当y,纵轴当x
{ //数组d不仅反映了距离,把他初始化为-1还可以当是否遍历过的标志
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
}
}
}
cout<<d[n][m]<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&g[i][j]);
memset(d,-1,sizeof(d));
bfs();
return 0;
}