#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m;
int f[N][N];
int main()
 {
    cin>>n>>m;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    memset(f, -1, sizeof(f));
    f[a-1][b-1]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    queue<pair<int,int>> q;
    q.push({a-1,b-1});
    while(!q.empty())
    {
         auto [y,x]=q.front();
         q.pop();
         if(y==c-1&&x==d-1)
           {
            cout<<f[y][x]<<'\n';
            return 0;
           }
         for(int i=0;i<4;i++)
         {
            int ny=y+dy[i];
            int nx=x+dx[i];
           
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&g[ny][nx]=='.'&&f[ny][nx]==-1)
            {
               f[ny][nx]=f[y][x]+1;
               q.push({ny,nx});
            }
         }
         
    }
     cout<<-1;
    
    return 0;

 }

// 64 位输出请用 printf("%lld")

1.BFS：

宽度搜索优先，一圈一圈的往外搜索，可以用来解决这题的最短距离问题。

思路：

从起点开始，把下一步可以走所有可能的情况，找到并且更新距离//也就是我们根据上一圈的情况把距离+1，比如

起点到起点的距离为零下一步到起点的距离就是0+1，以此类推，每一圈的情况依次+1//第一个到达终点的距离就是我们要找到的最短距离。

2.算法设计:

存储：

g[N][N]存地图

a,b,c,d存起点坐标(a,b)终点坐标(c,d);

//每种移动情况横纵坐标的变化

dy[4]={0，0，-1，1}

dx[4]={-1，1，0，0}

//我习惯y控制行x控制列

f[N][N]存地图上的点到起点的距离

队列queue<pair<int,int>>q;储存我们找到的最新一层的所有情况为后续往下寻找下一层做准备；

数据预处理：

数组下标：看个人习惯，我这里是0-based所以输入的起点终点下标都要-1，如果是1-based就不用了；

f数组初始化应该初始成什么？我这个代码中后面把f数组起点直接初始化为0了，其实按我这个memest写法初始化为零//代码中初始化为-1//也不会出错，因为不影响我们后面统计距离的逻辑。

核心代码讲解：

q.push({a-1,b-1});//从起点开始，起点放进队列中

while(!q.empty())//队列不为空，说明我们还可以继续寻找

{

auto [y,x]=q.front();//取出队头下标

q.pop();//已经考虑过的队头情况了直接删除

//判断是否到达终点

if(y==c-1&&x==d-1)

{

cout<<f[y][x]<<'\n';

return 0;

}

//没有到达终点就继续搜寻，遍历上下左右移动的所有情况

for(int i=0;i<4;i++)

{

//记录我们找到的新坐标

int ny=y+dy[i];

int nx=x+dx[i];

//新坐标是否满足我们的边界条件并且没有被访问过（不然会重复+1）

if(nx>=0&&nx<m&&ny>=0&&ny<n&&g[ny][nx]=='.'&&f[ny][nx]==-1)

{

f[ny][nx]=f[y][x]+1;//满足就更新距离

q.push({ny,nx});//把新的坐标存到队列里准备下一圈寻找

}

}

易错点：

1.数组开小，导致数据越界

2.距离的更新方式，基于上一圈的距离+1，如果用独立的变量记录距离比如t=0，t++；会导致距离出错。

3.0-based or 1-based数组下标；

4.memset数据初始化方法