BFS广度优先搜索

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<queue>  //使用队列需要的头文件（也可以用数组手动模拟队列）
#include<cstring>//使用memset()需要用到的头文件
using namespace std;

typedef pair<int ,int> PII;//定义坐标的数据结构

const int N=110;

int n,m;
char g[N][N];//存储地图
int d[N][N];//记录每个点到起点的距离

int bfs()
{
    queue <PII> q;//定义一个坐标队列
    q.push({0,0});//起点进队
    
    memset(d,-1,sizeof d);//距离初始化为- 1表示没有走过
    
    d[0][0]=0;//表示起点走过了
    
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};//向四个方向扩展的坐标数组(偏移量技巧)
    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];//（x,y）为走后的坐标
            //首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)
            //最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='.'&&d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;//更新未被访问的点到起点的距离（其实就是扩展前的点到起点的距离+1就行了）
                q.push({x,y}); //新坐标入队                          
            }
            
        }
    }
    return d[n-1][m-1];//输出右下角点据起点的距离即可
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];      
    
    
    printf("%d\n",bfs()+1);//包括起点就加1
    
    return 0;
}