网站更新提示ui怎末做,建一个网页网站,微信小程序开发软件,长沙装修公司性价比最高的是哪个洛谷 P1451 求细胞数量P1451 求细胞数量#xff0c;这绝对是 DFS统计连通块的入门天花板题 —— 吃透了能打通 Flood Fill 的任督二脉#xff01;今天就用最接地气的方式拆解这道题#xff0c;附上能直接 AC 的代码。题目核心#xff1a;给一个 n 行 m 列的矩阵#xff0c…洛谷 P1451 求细胞数量P1451 求细胞数量这绝对是 DFS统计连通块的入门天花板题 —— 吃透了能打通 Flood Fill 的任督二脉今天就用最接地气的方式拆解这道题附上能直接 AC 的代码。题目核心给一个 n 行 m 列的矩阵里面有数字1-9和 0数字代表细胞相邻上下左右的数字算同一个细胞要求统计矩阵里总共有多少个细胞。比如孤立的一个 5 算 1 个和它上下相连的 6、7 也算同一个最终只记 1 个。遍历矩阵遇到没被统计过的数字就用 DFS 把它所在的整个细胞区域标记掉每标记一次就计数 1。上代码#include bits/stdc.h using namespace std; char a[105][105]; int dx[]{1,0,-1,0},dy[]{0,1,0,-1},n,m,ans; void dfs(int x,int y){ a[x][y]0; for(int i0;i4;i){ int txxdx[i],tyydy[i]; if(a[tx][ty]1a[tx][ty]9){ dfs(tx,ty); } } } int main() { cinnm; for(int i0;in;i){ for(int j0;jm;j){ cina[i][j]; } } for(int i0;in;i){ for(int j0;jm;j){ if(a[i][j]!0){ dfs(i,j); ans; } } } coutans; return 0; }代码逻辑拆开来超简单数组开 105×105 是因为 n、m 最大 100留一点冗余避免越界dx、dy 数组是 DFS 的 “方向神器”代表上下左右四个移动方向新手记死这个组合就行DFS 函数的作用把当前细胞位置改成 0标记为已统计然后往四个方向找相邻的数字递归标记整个细胞区域 —— 相当于 “吃掉” 这个细胞主函数里遍历每个位置只要不是 0说明是未统计的细胞就调用 DFS 吃掉整个细胞然后计数 ans 加 1。举个例子矩阵里有 (0,0)1、(0,1)2、(1,0)3遍历到 (0,0) 时发现不是 0调用 DFS 会把 (0,0)、(0,1)、(1,0) 都改成 0ans1后续遍历到这些位置时因为是 0 就跳过最终只记 1 个细胞。这道题是连通块计数的 “母题”学会这个思路不管是数岛屿、数色块还是数其他连通区域都能照猫画虎。核心就是 “遇到一个算一个用 DFS 清掉一整片”新手多敲两遍就能熟练。总结解题核心遍历矩阵每发现一个未统计的细胞用 DFS 标记整个连通区域并计数 1DFS 作用将当前细胞及相邻的所有细胞标记为 0避免重复统计关键细节方向数组遍历上下左右判断条件精准匹配 1-9 的数字。