1 条题解
-
0
#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
- 上传者