洛谷 P1162 填涂颜色P1162 填涂颜色这个题一开始看着挺懵后来用 DFS一拆解发现核心逻辑其实超简单今天就把这个题的解题思路和代码分享给大家新手也能轻松看懂。先说说题目要求给一个 n×n 的方阵里面只有 0 和 11 代表围墙要求把所有被 1 包围的 0 改成 2而外围的 0 保持不变。比如一个 5×5 的方阵边缘的 0 没被包围中间被 1 围起来的 0 要标成 2。咋解决呢核心思路就一个先把 “外面” 的 0 找出来标记剩下的 0 就是被包围的。因为直接找被包围的 0 不好判断但找外围的 0 很容易 —— 从矩阵的边界比如 (0,0) 这个虚拟起点出发能走到的 0 都是 “外面” 的把这些 0 标记成 2最后再做一次替换标记成 2 的改回 0没被标记的 0 改成 21 保持不变。上代码亲测#include bits/stdc.h using namespace std; int a[35][35],dx[]{1,0,-1,0},dy[]{0,1,0,-1},n; void dfs(int x,int y){ for(int i0;i4;i){ a[x][y]2; int txxdx[i],tyydy[i]; if(tx0txn1ty0tyn1a[tx][ty]0)dfs(tx,ty); } } int main() { cinn; for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; } } dfs(0,0); for(int i1;in;i){ for(int j1;jn;j){ if(a[i][j]0)cout2 ; else if(a[i][j]2)cout0 ; else cout1 ; } coutendl; } return 0; }代码里的关键点很好理解数组开成 35×35 是因为 n 最大 30留一圈边界0 行、0 列、n1 行、n1 列方便从 (0,0) 开始搜索dx 和 dy 数组是上下左右四个方向DFS 的经典用法每次往四个方向走一步DFS 函数从 (0,0) 出发把能走到的 0 都标成 2—— 这些就是 “外围的 0”最后遍历矩阵的时候没被标 2 的 0被包围的输出 2标了 2 的 0外围的输出 01 照常输出。这个思路的妙处在于 “反向思考”不用纠结怎么判断 “被包围”而是先把不被包围的找出来剩下的自然就是目标。DFS 在这里就是用来 “遍历外围 0” 的工具递归的过程就是一步步把外围的 0 都标记完。新手写的时候注意两点一是数组边界要设到 n1别越界二是 DFS 里先标记当前点为 2再搜四个方向避免重复遍历。这个题是 DFS 入门的好题理解透了以后遇到类似的 “区域包围” 问题都能这么解。总结解题核心反向标记外围 0剩余 0 即为被包围的目标DFS 作用从矩阵边界 (0,0) 出发遍历并标记所有外围的 0最终处理标记为 2 的 0 改回 0未标记的 0 改成 21 保持不变。