题解 | #走迷宫#

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;//n行m列
int xs, ys, xt, yt;//起始点和目标点
char grid[1005][1005];//网格
int dist[1005][1005];//到此结点的最短距离
int gx[4] = { 0, 0, 1, -1 };
int gy[4] = { 1, -1, 0, 0 }; //上下左右四个方向
struct node {
    int x;
    int y;
};
bool inBound(int x, int y) {
    if (x > 0 && x <= n && y > 0 && y <= m) {
        return true;
    } else {
        return false;
    }
}

int bfs(int xs, int ys, int xt, int yt) {
    queue<node> q;
    q.push({ xs, ys });
    dist[xs][ys] = 0;
    while (!q.empty()) {
        node node = q.front();
        q.pop();
        if (node.x == xt && node.y == yt) {//判断是否为目标结点
            return dist[node.x][node.y];//返回最短路径
        }
        for (int i = 0; i < 4; i++) {
            int nx = node.x + gx[i];
            int ny = node.y + gy[i];
            if (dist[nx][ny] == -1 && inBound(nx, ny) &&
                    grid[nx][ny] == '.') { //判断新的结点有没有被遍历过，且没有超过网格的边界
                dist[nx][ny] = dist[node.x][node.y] + 1;//到此结点的最短路径
                q.push({ nx, ny });
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            dist[i][j] = -1;
        }
    if (grid[xt][yt] == '*')
        cout << -1 << endl;
    else
        cout << bfs(xs, ys, xt, yt) << endl;
    return 0;
}