题解 | 走迷宫

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

const int N = 1010;
char nums[N][N];
int idx[4] = {0, 0, 1, -1};  // 四个方向偏移量
int idy[4] = {1, -1, 0, 0};
bool vis[N][N] = {false};    // 访问标记
int cnt[N][N];               // 记录到每个位置的步数

int main() 
{
    int n, m, x1, y1, x2, y2;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    
    // 输入迷宫（坐标从1开始）
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> nums[i][j];
    
    // 检查起点是否为障碍
    if(nums[x1][y1] == '*') {
        cout << -1 << endl;
        return 0;
    }

    queue<pair<int, int>> q;
    q.push({x1, y1});
    vis[x1][y1] = true;  // 正确标记起点为已访问
    cnt[x1][y1] = 0;     // 初始化起点步数为0

    while(!q.empty())
    {
        int sz = q.size();
        for(int i = 0; i < sz; i++)
        {
            auto x = q.front();
            q.pop();

            // 若到达终点，提前退出
            if (x.first == x2 && x.second == y2) {
                cout << cnt[x2][y2] << endl;
                return 0;
            }

            // 探索四个方向
            for(int k = 0; k < 4; k++)
            {
                int a = x.first + idx[k];
                int b = x.second + idy[k];

                // 检查边界、是否访问过、是否可通行（.表示可走）
                if(a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && nums[a][b] == '.')
                {
                    q.push({a, b});
                    cnt[a][b] = cnt[x.first][x.second] + 1;  // 步数+1
                    vis[a][b] = true;
                }
            }
        }
    }
    
    // 若终点不可达
    cout << -1 << endl;
    return 0;
}