给定一个n\times mn×m的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(x_s,y_s)(xs​,ys​)到(x_t,y_t)(xt​,yt​)最少的移动次数。若不能到达，输出-1−1。

输入描述：

第一行输入两个整数n,mn,m (1\le n, m \le 10001≤n,m≤1000)，表示网格大小。
第二行输入四个整数x_s,y_s,x_t,y_txs​,ys​,xt​,yt​ (1\le x_s, x_t \le n1≤xs​,xt​≤n, 1\le y_s, y_t \le m1≤ys​,yt​≤m)，表示起点和终点的坐标。
接下来的nn行，每行输入一个长度为mm的字符串。其中，第ii行第jj个字符表示第ii行第jj列的格子上的障碍物情况，若字符为'*'，则格子上有障碍物，若字符为'.'，则格子上没有障碍物。
保证起点不存在障碍物。

输出描述：

输出一行一个整数，表示从(x_s,y_s)(xs​,ys​)到(x_t,y_t)(xt​,yt​)最少的移动次数。

示例1

输入：

5 5
1 1 5 5
.....
****.
.....
**.**
.....

示例2

输入：

5 5
1 1 4 5
.....
****.
.....
**.**
.....

输出：

-1

示例3

输入：

5 5
1 1 5 5
.....
****.
.....
*****
.....

输出：

-1

#include
#include
using namespace std;

typedef pairPII;
const int N = 1010;
char arr[N][N];
int d[N][N];
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };
int a, b;
int x00, y00, x11, y11;            //不能设置变量为x1，y1

int bfs()
{
    queueq;
    q.push({ x00,y00 });            //一定不要忘记给队列赋初始值！！！
    memset(d, -1, sizeof d);
    d[x00][y00] = 0;
    int x, y;
    while (q.size())
    {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            x = dx[i] + t.first, y = dy[i] + t.second;
            if (x >= 1 && x <= a && y >= 1 && y <= b && d[x][y]==-1 && arr[x][y] == '.')
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({ x,y });
            }
        }
    }
    return d[x11][y11] ;
}

int main() {
    cin >> a >> b;
    cin >> x00 >> y00 >> x11 >> y11;
    for (int i = 1; i <= a; i++)
    {
        for (int j = 1; j <= b; j++)
        {
            cin >> arr[i][j];
        }
    }
    if (bfs() == 0)cout << -1 << endl;
    else cout << bfs() << endl; 
}