输入样例:
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
期望输出:
8
代码实现:
#include<bits/stdc++.h> using namespace std;typedef pair<int,int> pii; const int N = 110;int n ,m; int s[N][N];//用存放地图 int d[N][N];//用于存放每个点到起点的距离 pii q[N*N];//定义一个队列,手动模拟int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0};int bfs() {int h=0,t=0;//队头和队尾q[0]={0,0};memset(d,-1,sizeof(d));//把所有点距离置为-1表示没有走过。d[0][0]=0;//起点自身的距离是0while(h<=t)//队列非空{auto k = q[h++];//取出队头//尝试往上下左右四个方向扩展for(int i=0;i<4;i++){int x = k.first + dx[i];int y = k.second + dy[i];//判断 点是否在范围内 并且 可以走 并且 没走过if(x>=0 && x<n && y>=0 && y<m &&s[x][y]==0 &&d[x][y]==-1){d[x][y]=d[k.first][k.second]+1;q[++t] = {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>>s[i][j];}}cout<<bfs()<<endl;}