记录158#includebits/stdc.h using namespace std; int mp[35][35]; bool vis[35][35]; int dx[4]{-1,0,1,0}; int dy[4]{0,1,0,-1}; int n; void dfs(int x,int y){ //从地图不涉及的外围来进行渗透 vis[x][y]1; for(int i0;i4;i){ int nxxdx[i]; int nyydy[i]; if(nx0nxn1ny0nyn1vis[nx][ny]0mp[nx][ny]0){ vis[nx][ny]1; dfs(nx,ny); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1;in;i){ for(int j1;jn;j){ cinmp[i][j]; } } dfs(0,0); //提前染色外部区域 for(int i1;in;i){ for(int j1;jn;j){ if(vis[i][j]0mp[i][j]0) cout2 ; else coutmp[i][j] ; } cout\n; } return 0; } //从扩大地图从最外层开始的原因特殊情况 //1 0 1 //0 1 0 //1 0 1 //预防这种情况题目传送门https://www.luogu.com.cn/problem/P1162前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的网格图搜索DFS/BFS与逆向思维结合的问题。问题转化逆向思维题目要求找出闭合圈内部的 0 并涂成 2。直接去搜索内部区域是非常困难的因为闭合圈形状任意很难确定一个绝对在内部的起点。因此我们采用逆向思维既然内部很难找那我们就去标记外部只要是从矩阵边界出发能够走到的所有 0一定都在闭合圈的外部。剩下的、没有被标记过的 0就必然是闭合圈内部的 0将它们涂成 2 即可。算法设计虚拟边界与 DFS 渗透为了处理边界上的 0我们在原矩阵的外围人为地“扩大”一圈将搜索的起点设置在(0,0)这个虚拟的外围点。从(0,0)出发进行深度优先搜索DFS只要遇到 0 且没有越界就继续向上下左右四个方向渗透并用vis数组将这些外部 0 标记为已访问。搜索结束后遍历原矩阵凡是mp[i][j]0且vis[i][j]0的点就是被圈住的内部 0。代码分块详细解释1. 全局变量与方向数组定义#includebits/stdc.h using namespace std; int mp[35][35]; bool vis[35][35]; int dx[4]{-1,0,1,0}; int dy[4]{0,1,0,-1}; int n;详细分析mp数组用于存储输入的 0/1 矩阵vis数组用于记录哪些格子已经被搜索过即属于外部区域。dx和dy是经典的四方向偏移数组分别代表上、右、下、左四个方向的坐标变化量。2. 核心逻辑DFS 外部渗透void dfs(int x, int y){ // 从地图不涉及的外围来进行渗透 vis[x][y] 1; for(int i 0; i 4; i){ int nx x dx[i]; int ny y dy[i]; if(nx 0 nx n1 ny 0 ny n1 vis[nx][ny] 0 mp[nx][ny] 0){ vis[nx][ny] 1; dfs(nx, ny); } } }详细分析这是本题的精髓。越界与边界处理注意if条件中的边界判断是nx 0 nx n1。因为原矩阵是1到n所以0和n1是人为扩大的虚拟边界。这保证了搜索可以在外围畅通无阻。渗透条件只有当目标点在合法范围内、未被访问过vis[nx][ny]0且是 0mp[nx][ny]0时才能继续渗透。遇到 1闭合圈的墙壁则自动被阻挡。3. 主函数数据读入与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cin n; for(int i 1; i n; i){ for(int j 1; j n; j){ cin mp[i][j]; } } dfs(0, 0); // 提前染色外部区域详细分析读入 n×n的矩阵。随后直接调用dfs(0, 0)从虚拟的左上角外围点开始将所有与外界连通的 0 全部标记为外部区域。4. 结果输出与内部填充for(int i 1; i n; i){ for(int j 1; j n; j){ if(vis[i][j] 0 mp[i][j] 0) cout 2 ; else cout mp[i][j] ; } cout \n; } return 0; }详细分析遍历原矩阵的 1 到 n 范围。如果当前点是 0 且没有被vis标记过说明它既不是外部的 0也不是 1 墙壁那么它一定是闭合圈内部的 0直接输出 2否则原样输出该点的值。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点逆向思维标记外部而非内部将“寻找内部连通块”转化为“寻找外部连通块”避免了寻找内部起点困难的问题外部起点(0,0)是绝对安全的虚拟边界nx 0 nx n1将搜索范围扩大到原矩阵外围的一圈完美处理了原矩阵边界上就是 0 的特殊情况防止漏判DFS渗透dfs(nx, ny)沿着 0 的路径向四周蔓延自动绕开 1墙壁精准标记出所有与外界连通的 0内部判定vis[i][j]0 mp[i][j]0寻找未被标记的 0利用排除法剩下的 0 必然是被 1 完全包围的内部空间原地输出cout 2 在输出阶段直接完成涂色无需修改原数组节省了空间逻辑更加清晰
P1162 填涂颜色
发布时间：2026/7/24 3:36:49
记录158#includebits/stdc.h using namespace std; int mp[35][35]; bool vis[35][35]; int dx[4]{-1,0,1,0}; int dy[4]{0,1,0,-1}; int n; void dfs(int x,int y){ //从地图不涉及的外围来进行渗透 vis[x][y]1; for(int i0;i4;i){ int nxxdx[i]; int nyydy[i]; if(nx0nxn1ny0nyn1vis[nx][ny]0mp[nx][ny]0){ vis[nx][ny]1; dfs(nx,ny); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; for(int i1;in;i){ for(int j1;jn;j){ cinmp[i][j]; } } dfs(0,0); //提前染色外部区域 for(int i1;in;i){ for(int j1;jn;j){ if(vis[i][j]0mp[i][j]0) cout2 ; else coutmp[i][j] ; } cout\n; } return 0; } //从扩大地图从最外层开始的原因特殊情况 //1 0 1 //0 1 0 //1 0 1 //预防这种情况题目传送门https://www.luogu.com.cn/problem/P1162前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的网格图搜索DFS/BFS与逆向思维结合的问题。问题转化逆向思维题目要求找出闭合圈内部的 0 并涂成 2。直接去搜索内部区域是非常困难的因为闭合圈形状任意很难确定一个绝对在内部的起点。因此我们采用逆向思维既然内部很难找那我们就去标记外部只要是从矩阵边界出发能够走到的所有 0一定都在闭合圈的外部。剩下的、没有被标记过的 0就必然是闭合圈内部的 0将它们涂成 2 即可。算法设计虚拟边界与 DFS 渗透为了处理边界上的 0我们在原矩阵的外围人为地“扩大”一圈将搜索的起点设置在(0,0)这个虚拟的外围点。从(0,0)出发进行深度优先搜索DFS只要遇到 0 且没有越界就继续向上下左右四个方向渗透并用vis数组将这些外部 0 标记为已访问。搜索结束后遍历原矩阵凡是mp[i][j]0且vis[i][j]0的点就是被圈住的内部 0。代码分块详细解释1. 全局变量与方向数组定义#includebits/stdc.h using namespace std; int mp[35][35]; bool vis[35][35]; int dx[4]{-1,0,1,0}; int dy[4]{0,1,0,-1}; int n;详细分析mp数组用于存储输入的 0/1 矩阵vis数组用于记录哪些格子已经被搜索过即属于外部区域。dx和dy是经典的四方向偏移数组分别代表上、右、下、左四个方向的坐标变化量。2. 核心逻辑DFS 外部渗透void dfs(int x, int y){ // 从地图不涉及的外围来进行渗透 vis[x][y] 1; for(int i 0; i 4; i){ int nx x dx[i]; int ny y dy[i]; if(nx 0 nx n1 ny 0 ny n1 vis[nx][ny] 0 mp[nx][ny] 0){ vis[nx][ny] 1; dfs(nx, ny); } } }详细分析这是本题的精髓。越界与边界处理注意if条件中的边界判断是nx 0 nx n1。因为原矩阵是1到n所以0和n1是人为扩大的虚拟边界。这保证了搜索可以在外围畅通无阻。渗透条件只有当目标点在合法范围内、未被访问过vis[nx][ny]0且是 0mp[nx][ny]0时才能继续渗透。遇到 1闭合圈的墙壁则自动被阻挡。3. 主函数数据读入与启动搜索int main(){ ios::sync_with_stdio(false); cin.tie(0); cin n; for(int i 1; i n; i){ for(int j 1; j n; j){ cin mp[i][j]; } } dfs(0, 0); // 提前染色外部区域详细分析读入 n×n的矩阵。随后直接调用dfs(0, 0)从虚拟的左上角外围点开始将所有与外界连通的 0 全部标记为外部区域。4. 结果输出与内部填充for(int i 1; i n; i){ for(int j 1; j n; j){ if(vis[i][j] 0 mp[i][j] 0) cout 2 ; else cout mp[i][j] ; } cout \n; } return 0; }详细分析遍历原矩阵的 1 到 n 范围。如果当前点是 0 且没有被vis标记过说明它既不是外部的 0也不是 1 墙壁那么它一定是闭合圈内部的 0直接输出 2否则原样输出该点的值。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点逆向思维标记外部而非内部将“寻找内部连通块”转化为“寻找外部连通块”避免了寻找内部起点困难的问题外部起点(0,0)是绝对安全的虚拟边界nx 0 nx n1将搜索范围扩大到原矩阵外围的一圈完美处理了原矩阵边界上就是 0 的特殊情况防止漏判DFS渗透dfs(nx, ny)沿着 0 的路径向四周蔓延自动绕开 1墙壁精准标记出所有与外界连通的 0内部判定vis[i][j]0 mp[i][j]0寻找未被标记的 0利用排除法剩下的 0 必然是被 1 完全包围的内部空间原地输出cout 2 在输出阶段直接完成涂色无需修改原数组节省了空间逻辑更加清晰
)
