本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4501 [GESP202603 四级] 山之谷 - 洛谷【题目描述】现有一片山地可以视为一个N NN行M MM列的网格图第i ii行j jj列的海拔为h i , j h_{i,j}hi,j​。如果一个单元格的海拔不高于其所有相邻单元格相邻包括上、下、左、右、左上、右上、左下、右下最多8 88个方向的海拔则称该单元格为山谷。请你数一数该片山地中有多少山谷。【输入】第一行包含2 22个整数N , M N, MN,M表示山地的大小。之后N NN行每行包含M MM个整数h i , 1 , h i , 2 , ⋯ , h i , M h_{i,1}, h_{i,2}, \cdots, h_{i,M}hi,1​,hi,2​,⋯,hi,M​表示海拔。【输出】输出1 11行包含1 11个整数C CC表示山谷的数量。【输入样例】3 5 7 6 6 7 9 6 5 6 7 6 6 5 7 8 9【输出样例】3【核心思想】问题分析给定N × M N \times MN×M的海拔网格需要统计山谷数量。山谷定义为海拔不高于所有8 88个方向相邻单元格上、下、左、右及四个对角线方向的单元格。这是一个网格遍历 方向枚举问题核心在于对每个单元格检查其8 88个邻居的海拔关系。算法选择方向向量枚举预定义8 88个方向的偏移量( d x k , d y k ) (dx_k, dy_k)(dxk​,dyk​)统一处理所有相邻位置逐格判定遍历每个单元格检查其所有合法邻居是否均≥ \geq≥当前单元格海拔关键步骤读入数据读取N , M N, MN,M和海拔矩阵h [ 1.. N ] [ 1.. M ] h[1..N][1..M]h[1..N][1..M]方向数组定义d x [ − 1 , − 1 , − 1 , 0 , 1 , 1 , 1 , 0 ] dx [-1, -1, -1, 0, 1, 1, 1, 0]dx[−1,−1,−1,0,1,1,1,0]d y [ − 1 , 0 , 1 , 1 , 1 , 0 , − 1 , − 1 ] dy [-1, 0, 1, 1, 1, 0, -1, -1]dy[−1,0,1,1,1,0,−1,−1]对应8 88个相邻方向逐格判定山谷遍历i ii从1 11到N NNj jj从1 11到M MMf l a g ← t r u e flag \leftarrow trueflag←true遍历8 88个方向计算邻居坐标( n x , n y ) ( i d x k , j d y k ) (nx, ny) (i dx_k, j dy_k)(nx,ny)(idxk​,jdyk​)若邻居在边界内且h n x , n y h i , j h_{nx,ny} h_{i,j}hnx,ny​hi,j​f l a g ← f a l s e flag \leftarrow falseflag←falseb r e a k breakbreak若f l a g t r u e flag trueflagtruec n t ← c n t 1 cnt \leftarrow cnt 1cnt←cnt1输出结果c n t cntcnt时间/空间复杂度时间复杂度O ( N ⋅ M ) O(N \cdot M)O(N⋅M)每个单元格检查8 88个方向共8 N M 8NM8NM次比较空间复杂度O ( N ⋅ M ) O(N \cdot M)O(N⋅M)存储海拔矩阵方向枚举与边界处理的核心思想统一方向处理通过预定义8 88个方向向量将不同方向的邻居检查统一为坐标加法运算避免重复编写边界判断逻辑提前终止优化一旦发现某个邻居海拔严格小于当前单元格立即判定不是山谷并跳出循环减少不必要的比较边界安全判定通过n x ∈ [ 1 , N ] nx \in [1,N]nx∈[1,N]且n y ∈ [ 1 , M ] ny \in [1,M]ny∈[1,M]的条件过滤越界邻居确保不会访问数组非法位置不严格小于的判定题目要求不高于所有相邻单元格即h i , j ≤ h n e i g h b o r h_{i,j} \leq h_{neighbor}hi,j​≤hneighbor​对所有邻居成立等价于不存在邻居h n e i g h b o r h i , j h_{neighbor} h_{i,j}hneighbor​hi,j​适用于网格图上的局部极值统计、邻域关系判定类基础问题【算法标签】#普及- #模拟【代码详解】#includebits/stdc.h// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN105;// 定义常量N表示数组最大尺寸intn,m,cnt;// n:行数, m:列数, cnt:山谷计数器inta[N][N];// 定义二维数组a存储地形高度// 定义8个方向向量用于访问当前位置周围的8个邻居intdx[8]{-1,-1,-1,0,1,1,1,0};// x方向偏移左、左上、上、右上、右、右下、下、左下intdy[8]{-1,0,1,1,1,0,-1,-1};// y方向偏移上、上、上、右、右、右、下、下intmain()// 主函数入口{cinnm;// 输入矩阵的行数n和列数m// 读取矩阵数据for(inti1;in;i){for(intj1;jm;j){cina[i][j];// 读取第i行第j列的高度}}// 遍历矩阵中的每一个位置for(inti1;in;i){for(intj1;jm;j){boolflag1;// 标志位表示当前位置是否是山谷初始化为true// 检查当前位置的8个邻居for(intk0;k8;k){// 计算邻居位置的坐标intnxidx[k];// 邻居的x坐标intnyjdy[k];// 邻居的y坐标// 检查邻居是否在矩阵范围内if(nx1||nxn||ny1||nym){continue;// 如果邻居越界跳过这个邻居}// 检查山谷条件如果邻居高度小于当前位置高度则不是山谷if(a[nx][ny]a[i][j]){flag0;// 标记当前位置不是山谷break;// 提前退出循环不再检查其他邻居}}// 如果flag仍为1说明所有邻居都不小于当前位置当前位置是山谷if(flag){cnt;// 山谷计数器加1}}}coutcntendl;// 输出山谷的总数量return0;// 程序正常结束}【运行结果】3 5 7 6 6 7 9 6 5 6 7 6 6 5 7 8 9 3