题解 | 走迷宫

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

bool BFS(int x_s, int y_s, int x_t, int y_t, const vector<string>& grid,
         vector<vector<int>>& dist) {
    int n = grid.size();
    int m = grid[0].size();

    queue<pair<int, int>> q;
    q.push({x_s, y_s});
    dist[x_s][y_s] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == x_t && y == y_t) {
            return true;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (grid[nx][ny] == '.' && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    int x_s, y_s, x_t, y_t;
    cin >> x_s >> y_s >> x_t >> y_t;
    x_s--;
    y_s--;
    x_t--;
    y_t--;

    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    // 根据题目保证，起点一定不是障碍物，无需处理

    if (BFS(x_s, y_s, x_t, y_t, grid, dist)) {
        cout << dist[x_t][y_t] << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}