1 条题解

  • 0
    @ 2026-1-27 22:07:15
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] n-地图的行数;m-地图的列数;p1,p2-泉水的初始位置(输入为1-based坐标)
    int n,m,p1,p2;
    // [2] arr数组-存储每个格子的高度(0-based坐标),-1表示该格子已被淹没(已访问)
    int arr[1100][1100];
    
    // [3] 队列存储的坐标结构体(用于BFS遍历被淹没的格子)
    struct stu{
        int x,y;
    };
    queue<stu> q;  // [4] BFS队列,存储待处理的被淹没格子坐标
    
    // [5] 四个方向的偏移量(右、下、左、上)
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    
    void bfs(){
        // 1. 获取泉水的初始高度(输入为1-based,转换为0-based坐标后取值)
        int a=arr[p1-1][p2-1];
        // 2. 初始化BFS:起点入队,标记为已淹没(-1),初始淹没格子数为1(起点自身)
        q.push({p1-1,p2-1});
        arr[p1-1][p2-1]=-1;
        int sum=1;
    
        // 3. BFS核心循环:处理队列中的所有被淹没格子
        while(!q.empty()){
            stu b=q.front();  // [6] 取出队首的当前格子坐标
            q.pop();  // [7] 队首元素出队
    
            // 4. 遍历四个方向的相邻格子
            for(int i=0;i<4;i++){
                int tx=b.x+dx[i];  // [8] 计算相邻格子的横坐标
                int ty=b.y+dy[i];  // [9] 计算相邻格子的纵坐标
                // 合法性判断:1.坐标在地图范围内;2.格子高度≤泉水高度;3.未被淹没(不是-1)
                if((tx>=0 && tx<n) && (ty>=0 && ty<m) && arr[tx][ty]<=a && arr[tx][ty]!=-1){
                    sum++;  // [10] 淹没格子数+1
                    arr[tx][ty]=-1;  // [11] 标记该格子为已淹没(避免重复访问)
                    q.push({tx,ty});  // [12] 相邻格子入队,继续扩展淹没范围
                }
            }
        }
        cout<<sum;  // [13] 输出被淹没的总格子数
    }
    
    int main(){
        cin>>n>>m>>p1>>p2;  // [14] 读取地图的行数、列数,以及泉水的1-based初始位置
        // 读取每个格子的高度(0-based坐标存储)
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>arr[i][j];
        bfs();  // [15] 调用BFS计算被淹没的格子数
        return 0;
    }
    
    • 1

    信息

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