2 条题解

  • 0
    @ 2025-3-2 15:18:24

    注意!!

    狡猾的y1函数会伪装成变量诱导你

    实在可恶!!!

    #include <bits/stdc++.h>
    using namespace std;
    int n;
    char a[1007][1007];
    int x1, y11, x2, y2;
    struct node {
        int x;
        int y;
        int steps;
    };
    int xo[4] = {1, 0, 0, -1};  //x方向
    int yo[4] = {0, -1, 1, 0};  //y方向
    queue<node> op;
    int minstep = 99999999;  //初始化为一个很大的值
    //BFS
    void bfs(int x1, int y1) {
        //检查起点和终点是否是障碍物
        if (a[x1][y11] == '1' || a[x2][y2] == '1') {
            minstep = -1;  //是障碍,无法到达
            return;
        }
        op.push(node{x1, y11, 0});
        a[x1][y1] = '1';  // 标记起点为已访问
        while (!op.empty()) {
            node tou = op.front();
            op.pop();
            if (tou.x == x2 && tou.y == y2) {
                minstep = tou.steps;
                return;  // 找到目标点,提前返回
            }
            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int xx = tou.x + xo[i];
                int yy = tou.y + yo[i];
                // 检查越界和是否访问过 
                if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '0') {
                    a[xx][yy] = '1';  // 标记该位置为已访问
                    op.push(node{xx, yy, tou.steps + 1});
                }
            }
        }
    }
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> a[i][j];
            }
        }
        cin >> x1 >> y11 >> x2 >> y2;
        x1--; y11--; x2--; y2--;  // 坐标从1开始,转换为从0开始的索引
        bfs(x1, y11);
        // 如果 minstep 仍是初始值,表示没有找到路径
        if (minstep == 99999999) {
            cout << "-1" << endl;  // 无法到达目标(好像有点多余,题里头没要求)
        } else {
            cout << minstep;  // 输出最短路径的步数
        }
        return 0;
    }
    //bfs真好玩!! 
    
    

    信息

    ID
    5804
    时间
    1000ms
    内存
    125MiB
    难度
    2
    标签
    递交数
    20
    已通过
    7
    上传者