C++STL
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 110;
int n,m;
typedef pair<int,int> PII;
int g[N][N];//存储地图
int d[N][N];//存储距离
queue<PII> q;
int bfs()
{
memset(d,-1,sizeof(d));
q.push({0,0}); //起点加入队列
d[0][0]=0; //初始点的距离为 0.
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(!q.empty())
{
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(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
{
//从当前点走过去,则距离等于当前点的距离+1
d[x][y]=d[t.first][t.second]+1;
//这个点放入队列,用来走到和它相邻的点
q.push({x,y});
}
}
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs()<<endl;
return 0;
}
手动模拟队列
tt是初始-1,y总也习惯-1,但是这里是从起点开始q[0] = {0,0}; //此时默认将起点加入队列了
由于q[++ tt] = x;
所以tt变成了 -1 + 1 = 0 ,所以初始化的时候hh = 0, tt = 0; //队列中已经有一个元素了hh~
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n,m;
typedef pair<int,int> PII;
int g[N][N],d[N][N];
PII q[N*N];
int bfs()
{
memset(d,-1,sizeof(d));
int tt=0,hh=0;
q[0]={0,0};
d[0][0]=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
{
d[x][y]=d[t.first][t.second]+1;
q[++tt]={x,y};
}
}
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
cout<<bfs()<<endl;
return 0;
}