整站优化温州怎么做?,wordpress后台主题无法管理,网站建设项目公司,服装网站开发东方博宜 1435 数池塘#xff08;八方向#xff09;把四方向连通改成了八方向#xff0c;核心逻辑没变#xff0c;但细节上有小调整#xff0c;新手只要吃透 DFS 的本质#xff0c;分分钟拿捏#xff01;今天就用最接地气的方式拆解这道题#xff0c;附上能直接 AC 的代…东方博宜 1435 数池塘八方向把四方向连通改成了八方向核心逻辑没变但细节上有小调整新手只要吃透 DFS 的本质分分钟拿捏今天就用最接地气的方式拆解这道题附上能直接 AC 的代码。题目核心给一个 n 行 m 列的矩阵里面只有 W水和 .陆地相邻上下左右 斜对角共 8 个方向的 W 算同一个池塘要求统计矩阵里总共有多少个池塘。比如斜着挨在一起的两个 W 算一个池塘这也是和四方向题最核心的区别。遍历矩阵遇到没被统计的 W 就用 DFS 把它所在的整个池塘区域标记掉每标记一次计数 1唯一的变化是搜索方向从 4 个变成了 8 个。上代码#include bits/stdc.h using namespace std; char mp[1005][1005]; int n,m,dx[]{1,1,0,-1,-1,-1,0,1},dy[]{0,1,1,1,0,-1,-1,-1},ans; void dfs(int x,int y){ mp[x][y].; for(int i0;i8;i){ int txxdx[i],tyydy[i]; if(mp[tx][ty]W)dfs(tx,ty); } } int main() { cinnm; for(int i0;in;i){ for(int j0;jm;j){ cinmp[i][j]; } } for(int i0;in;i){ for(int j0;jm;j){ if(mp[i][j]W){ dfs(i,j); ans; } } } coutans; return 0; }代码逻辑拆开来超易懂数组开 1005×1005 是因为 n、m 最大 1000留冗余避免越界dx、dy 数组是这道题的关键 ——8 个元素对应 8 个方向下、右下、右、右上、上、左上、左、左下新手可以记死这个组合八方向题直接用DFS 函数的作用把当前池塘位置改成 .标记为已统计然后往 8 个方向找相邻的 W递归标记整个池塘区域主函数遍历每个位置只要是 W未统计的池塘就调用 DFS 吃掉整个池塘ans 加 1。举个例子矩阵里 (0,0)W、(0,1)W、(1,0)W遍历到 (0,0) 时调用 DFS会把这三个位置都改成 .ans1后续遍历到这些位置时直接跳过最终只记 1 个池塘。踩坑提醒千万别把方向数组写成 4 个这是八方向题最容易犯的错DFS 里先改当前位置再搜八个方向防止重复统计同一个池塘。这道题是八连通区域计数的经典题学会这个思路不管是数池塘、数油田还是数其他八连通区域都能直接套用。核心就是 “方向数组扩到 8 个其余逻辑和四方向完全一样”新手多敲两遍就能熟练。总结解题核心遍历矩阵每发现一个未统计的 W用 DFS 标记整个八连通区域并计数 1关键调整方向数组从 4 个扩展到 8 个覆盖上下左右 斜对角DFS 作用将当前 W 及八方向相邻的所有 W 标记为 .避免重复统计。