D2-走迷宫

题目描述

思路分析

维护一个队列，每次从队列中取出一个元素，然后从这个元素的四个方向进行遍历、判断是否出界和这个位置是否能走，使用bfs遍历一遍后得出的值就是最短路径

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n,m,g[N][N],d[N][N];//d数组维护从{0，0}到{x,y}的距离
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
typedef pair<int,int> p;
int bfs()
{
  queue<p>  q;
  //首先将d数组重置
  memset(d,-1,sizeof d);
  //先将第一个元素入队
  q.push({0,0});
  d[0][0]=0;
  while(q.size())
  {
  //取出队首元素
    p 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)
      {
        q.push({x,y});
        d[x][y] = d[t.first][t.second] + 1;
      }
    }
  }
  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];
  int res = bfs();
  cout<<res<<endl;
  return 0;

}