洛谷P1162 填涂颜色

最新推荐文章于 2022-12-27 22:13:02 发布
最新推荐文章于 2022-12-27 22:13:02 发布
阅读量270 收藏
点赞数
分类专栏： 《算法刷题》 文章标签： 洛谷 DFS
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Junyi727/article/details/125053335
版权
这篇博客介绍了洛谷P1162问题，涉及在一个由0和1组成的方阵中，如何用DFS算法将闭合圈内的0全部填充为2。题目要求闭合圈由1构成，且至少包含一个0。博客内容包括题目描述、输入输出格式、样例以及解题思路。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

目录

洛谷P1162 填涂颜色

题目描述

输入格式

输出格式

输入输出样例

说明/提示

解题思路：

洛谷P1162 填涂颜色

题目链接：洛谷P1162 填涂颜色

题目描述

由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1≤n≤30)

接下来n行，由0和1组成的n×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式

已经填好数字2的完整方阵。

最低0.47元/天 解锁文章
信奥赛CSP-J复赛集训（dfs专题）（2）：洛谷P1162：填涂颜色
王老师青少年编程
12-02 1031
信奥赛CSP-J复赛集训（dfs专题-刷题题单及题解）（2）：洛谷P1162：填涂颜色
18719 填涂颜色
weixin_45842941的博客
04-09 811
由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。 现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下： 涂色前： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 涂色后： 0 0 0 0 0 0 0 0 1 1 1 1 ...
P1162 填涂颜色
森宝的博客
03-20 509
题目描述 由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0...
洛谷 P1162 填涂颜色（巧妙DFS）
wait
09-21 631
题目描述 由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0...
填涂颜色【洛谷P1162】
ESTHERWXY的博客
06-28 270
题目描述 由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 ...
洛谷P1162 填涂颜色（Python搜索）
辞树
03-08 382
P1162 填涂颜色https://www.luogu.com.cn/problem/P1162 题目描述 由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0
洛谷—P1162 填涂颜色题解
NCU_tanghulu的博客
10-14 573
题目链接：P1162 填涂颜色 解题思路： 用DFS搜索，用vis数组记录当前点有没有访问过。如果没有就输出2，否则输出0。实际上这是不对的。看下面： 我们的判断数组是这个样子，从DFS（1,1）开始搜索 bool check(int x, int y) { if (x<1 || x>n || y<1 || y>n) { return 0; } return 1; } 然后提交会发现过不了。这是因为dfs在先搜索的时候应该搜索到矩阵的外面一圈（0， n + 1） 否则的话
P1162 填涂颜色（BFS）
qq_43738331的博客
01-31 505
题目描述 由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6）， 涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1 输入格式 每组测试数据
P1162 填涂颜色
yanpanyan的博客
05-14 368
题目描述 由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0...
洛谷[P1162 填涂颜色]
aaaghyaa的博客
05-20 264
洛谷 [P1162 填涂颜色] https://www.luogu.com.cn/problem/P1162#submit 题目: 思路: 先遍历一遍边框,把边框上为 000 的数字为起点进行深度搜索(因为在边框上,说明没有被111围住),把遇到的所有000标记为 −1-1−1 然后再输出即可,遇到−1-1−1则输出000,遇到000(说明这个000是被111包围起来的)则输出222,111的输出不变 代码: #include<bits/stdc++.h> using namespace st
洛谷——p1162 填涂颜色
明里灰的博客
12-27 779
由数字 0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 构成，围圈时只走上下左右 4 个方向。这个题目首先我想的是遍历地图，如果每个点的上下左右都可以找到‘ 1 ’ ，那这个点就被 1 包围着。这是一个比较基础的搜索题，但是我想了挺久，然后第一个思路还是错的。接下来 n 行，由 0 和 1 组成的 n×n 的方阵。每组测试数据第一行一个整数 n(1≤n≤30)。方阵内只有一个闭合圈，圈内至少有一个 0。1 1 1 1 1 1（涂色前）1 1 1 1 1 1（涂色后）已经填好数字 2 的完整方阵。
洛谷 | P1162 填涂颜色
Wonz
03-26 656
搜索 专题 题目链接： 洛谷 P1162 填涂颜色 题目描述 输入输出格式 时空限制 时间：1000ms 空间：128MB 思路 其实我还不会 BFS ，看了题解，发现有人直接用 暴力 解决了，我就好奇试了一下，结果 AC 了。真的神奇。 初始化，把所有为 0 的先改成 2，然后在 BFS 里面，先判断外围的 2 要恢复成 0，然后二重循环，把不在圈内的 2 恢复成 0，如此循环 9...
洛谷-P1162 填涂颜色
qq_52011873的博客
11-14 354
题目链接 题目大意：给定地图，然后把地图中被1围起来的0变为2 解题思路：给点的地图为n * n，我们先将地图四周扩大为n+1*n+1填充0，然后我们从（1，1）出发用dfs遇见1停止，遇见0标记，地图中被1围起来的0我们用dfs进不去所以未标记，最后如果!flag[i][j]&&mapp[i][j]==0 我们输出2，否者就输出mapp[i][j] 注：将地图四周扩大为n+1*n+1填充0，是为了防止边缘都是1的情况。 #include<iostream> #include&l
洛谷p1162 填涂颜色
wans__的博客
12-01 468
题目描述 由数字0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6X6的方阵（n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1
洛谷 P1162 填涂颜色
片言可决讼，半纸能缚龙
05-20 965
题目链接：https://www.luogu.com.cn/problem/P1162 题目描述： 解题思路： 从每个边界0出发，把里面的1当成障碍，因为边界的0肯定不在环里，用深度优先或者广度优先搜索，把能到位置在bk数组里全置1，遍历完后bk数组里的0就是环里的0，将它置2. 代码如下： #include <bits/stdc++.h> using namespace std; int a[35][35]; int bk[35][35]; int f[4][2]= {{0,1},{0,
p1162 填涂颜色
Source_Roc
03-11 1475
题目链接：点击打开链接很经典的一道bfs（广度优先搜索）（我看大佬们说的）所以蒟蒻的我奉上两种思路描述：由数字0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6X6的方阵（n=6），涂色前和涂色后的方阵如下：0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0...
P1162 填涂颜色-洛谷（DFS）
Wty的刷题笔记
10-30 645
原题链接： https://www.luogu.com.cn/problem/P1162 题目描述 由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下： 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1
洛谷P1162题目的填涂颜色python
最新发布
03-30
### 关于洛谷 P1162 填涂颜色的 Python 解法 洛谷 P1162 的核心在于通过动态规划来解决问题。该问题可以被抽象成一个二维网格上的路径计数问题，其中每一步的选择受到前一步状态的影响[^1]。 以下是基于动态规划的思想实现的一个解法： #### 动态规划的状态定义 设 `dp[i][j]` 表示到达第 i 行 j 列时的不同填涂方案数量。由于每一格的颜色取决于其上一格和左一格的颜色，因此可以通过转移方程计算当前格子的可能性数目。 #### 转移方程 对于任意位置 `(i, j)`，如果它可以从上方 `(i-1, j)` 或左侧 `(i, j-1)` 移动过来，则有如下关系： \[ dp[i][j] = (dp[i-1][j] + dp[i][j-1]) \% mod \] 这里 `%mod` 是为了防止数值过大而取模操作，通常题目会指定一个较大的质数作为模数。 #### 边界条件 初始状态下，起点处只有一种方式到达自己，即 \( dp[0][0] = 1 \)；其他超出边界的情况均视为不可达，对应的值初始化为零。 下面是完整的 Python 实现代码： ```python def fill_color(n, m, k): MOD = int(1e9 + 7) # 初始化 DP 数组 dp = [[0] * (m + 1) for _ in range(n + 1)] dp[0][0] = 1 # 枚举每一个单元格并更新状态 for i in range(1, n + 1): for j in range(1, m + 1): if i == 1 and j == 1: # 特殊处理第一个格子 dp[i][j] = k % MOD else: dp[i][j] = ((k - 1) * (dp[i-1][j] + dp[i][j-1])) % MOD return dp[n][m] # 输入部分 n, m, k = map(int, input().split()) result = fill_color(n, m, k) print(result) ``` 此程序实现了上述逻辑，并能够高效地求解大规模输入下的结果。 --- #### 注意事项 在实际提交过程中需要注意以下几点： 1. 数据范围可能较大，需考虑优化空间复杂度。 2. 取模运算应贯穿整个过程以避免溢出错误。 3. 对于特殊情况（如单行或单列），可以直接给出结论而不必进入循环。 ---
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

程序员shy

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值