题解：洛谷 P2919 [USACO08NOV] Guarding the Farm S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2919 [USACO08NOV] Guarding the Farm S - 洛谷【题目描述】农场有许多小山丘约翰农夫希望在这些小山丘上放置守卫以确保他珍贵的奶牛的安全。他想知道如果他希望在每个小山丘的顶部放置一个守卫他需要多少守卫。他有一张地图这张地图是一个整数矩阵矩阵有N NN行1 N ≤ 700 1 N \leq 7001N≤700和M MM列1 M ≤ 700 1 M \leq 7001M≤700。矩阵中的每个元素表示一个高度H i j H_{ij}Hij​0 ≤ H i j ≤ 10 , 000 0 \leq H_{ij} \leq 10,0000≤Hij​≤10,000。请帮助他确定地图上有多少个山顶。一个山顶是由一个或多个相邻且具有相同值的矩阵元素组成这些元素被地图的边缘或具有较低较小高度的元素完全包围。如果两个不同的元素的X XX坐标差的绝对值不大于 1且Y YY坐标差的绝对值也不大于 1则它们是相邻的。【输入】* 第 1 行两个用空格分隔的整数N NN和M MM* 第 2 行到第N 1 N1N1行第i 1 i1i1行描述矩阵的第i ii行包含M MM个用空格分隔的整数H i j H_{ij}Hij​【输出】* 第 1 行一个整数表示山顶的数量【输入样例】8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0【输出样例】3【算法标签】#普及plus【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义坐标对类型constintN705;// 定义地图最大尺寸intn,m;// n: 行数m: 列数inth[N][N];// 存储每个点的高度boolvis[N][N];// 标记每个点是否被访问过// 八个方向的偏移量intdx[8]{-1,-1,-1,0,0,1,1,1};intdy[8]{-1,0,1,-1,1,-1,0,1};// 广度优先搜索函数判断(x,y)是否是山丘的最高点boolbfs(intx,inty){intvalh[x][y];// 记录当前连通块的高度值boolflagtrue;// 标记当前连通块是否满足山丘条件queuePIIq;// 定义队列用于BFSq.push({x,y});// 将起点加入队列vis[x][y]true;// 标记起点已访问while(!q.empty())// 当队列不为空时循环{intxxq.front().first,yyq.front().second;// 取出队首坐标q.pop();// 弹出队首for(inti0;i8;i)// 遍历八个方向{intnxxxdx[i],nyyydy[i];// 计算相邻坐标if(nx1||nxn||ny1||nym)// 检查边界continue;if(h[nx][ny]val)// 如果相邻点高度大于当前连通块高度flagfalse;// 不满足山丘条件if(h[nx][ny]val!vis[nx][ny])// 如果相邻点高度相同且未访问{q.push({nx,ny});// 加入队列vis[nx][ny]true;// 标记已访问}}}returnflag;// 返回当前连通块是否满足山丘条件}intmain(){cinnm;// 输入行数和列数for(inti1;in;i)// 读入高度图for(intj1;jm;j)cinh[i][j];intans0;// 山丘数量for(inti1;in;i)// 遍历整个地图for(intj1;jm;j){if(!vis[i][j])// 如果当前点未被访问{if(bfs(i,j))// 执行BFS判断是否是山丘ans;// 如果是山丘计数加1}}coutansendl;// 输出山丘数量return0;}【运行结果】8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0 3