1 条题解

  • 0
    @ 2026-1-27 21:37:51
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] n-迷宫的行数;m-迷宫的列数
    int n,m;
    // [2] arr数组-存储迷宫地图,0表示可走,1表示不可走/已访问
    int arr[200][200];
    // [3] q_x,q_y-起点坐标(0-based);z_x,z_y-终点坐标(0-based)
    int q_x,q_y,z_x,z_y;
    // [4] 四个方向的偏移量(右、下、左、上)
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    
    // [5] 队列存储的坐标结构体(用于BFS遍历节点)
    struct qtu{
        int x,y;
    }; 
    
    // [6] 栈存储的坐标结构体(用于回溯路径)
    struct vtu{
        int v_x,v_y;
    }; 
    
    // [7] 前驱坐标结构体(存储每个节点的父节点坐标,用于回溯路径)
    struct stu{
        int s_x,s_y;
    }brr[200][200];  // [8] brr数组-记录每个节点的前驱坐标
    
    queue<qtu> q;  // [9] BFS队列,存储待处理的节点坐标
    stack<vtu> v;  // [10] 路径栈,存储回溯后的路径坐标
    
    void bfs(){
        // 1. BFS初始化:起点入队,标记为已访问,设置起点前驱为-1(无父节点)
        q.push({q_x,q_y});
        arr[q_x][q_y]=1;  // [11] 标记起点为已访问(避免重复入队)
        brr[q_x][q_y]={-1,-1};  // [12] 起点无前驱,设为-1,-1
        
        // 2. 处理队列中的节点(BFS核心循环)
        while(!q.empty()){
            qtu a=q.front();
            q.pop();  // [13] 取出队首节点
            
            // 5. 判断是否到达终点:如果当前节点是终点,回溯路径并输出
            if(a.x==z_x && a.y==z_y){
                // 6. 回溯路径:从终点倒推到起点,存入栈中(栈的先进后出特性可让路径正序输出)
                int i=z_x,j=z_y;
                while(i!=-1 && j!=-1){
                    v.push({i,j});  // [14] 当前节点入栈
                    // 获取当前节点的前驱坐标,继续倒推
                    int a=brr[i][j].s_x;
                    int b=brr[i][j].s_y;
                    i=a;
                    j=b;
                } 
                // 7. 输出路径:从栈顶依次弹出(正序输出路径)
                while(!v.empty()){
                    int a=v.top().v_x;
                    int b=v.top().v_y;
                    v.pop();
                    // 输出1-based坐标(题目输入输出为1-based,代码处理为0-based,需转换)
                    cout<<"("<<a+1<<","<<b+1<<")"; 
                    if(!v.empty()) cout<<"->";  // [15] 非最后一个节点输出箭头连接
                } 
                return;
            } 
            
            // 3. 遍历四个方向,扩展当前节点的邻居
            for(int i=0;i<4;i++){
                int tx=a.x+dx[i];  // [16] 计算新节点的横坐标
                int ty=a.y+dy[i];  // [17] 计算新节点的纵坐标
                // 判断新节点是否在迷宫范围内,且未被访问(arr[tx][ty]==0)
                if((tx>=0 && tx<n) && (ty>=0 && ty<m) && arr[tx][ty]==0){
                    arr[tx][ty]=1;  // [18] 标记新节点为已访问
                    q.push({tx,ty});  // [19] 新节点入队
                    // 4. 记录新节点的前驱坐标(当前节点a是新节点的父节点)
                    brr[tx][ty].s_x=a.x;
                    brr[tx][ty].s_y=a.y; 
                }
            } 
        }
        // 8. 队列处理完毕仍未找到终点,输出"no way"
        cout<<"no way"; 
    }
    
    int main(){
        cin>>n>>m;  // [20] 读取迷宫的行数n和列数m
        // 读取迷宫地图
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>arr[i][j];
            }
        }
        // 读取起点和终点坐标(输入为1-based,转换为0-based)
        cin>>q_x>>q_y>>z_x>>z_y;
        q_x-=1,q_y-=1,z_x-=1,z_y-=1;  // [21] 1-based转0-based,适配代码中的坐标处理
        bfs();  // [22] 调用BFS寻找最短路径
        return 0;
    }
    
    • 1

    信息

    ID
    1310
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    6
    已通过
    1
    上传者