首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

BFS 颜色填涂———洛谷p1162

编程知识
2024年09月21日 15:39

填涂颜色

题目描述

由数字 \(0\) 组成的方阵中,有一任意形状的由数字 \(1\) 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 \(2\)。例如:\(6\times 6\) 的方阵(\(n=6\)),涂色前和涂色后的方阵如下:

如果从某个 \(0\) 出发,只向上下左右 \(4\) 个方向移动且仅经过其他 \(0\) 的情况下,无法到达方阵的边界,就认为这个 \(0\) 在闭合圈内。闭合圈不一定是环形的,可以是任意形状,但保证闭合圈内\(0\) 是连通的(两两之间可以相互到达)。

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

输入格式

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

接下来 \(n\) 行,由 \(0\)\(1\) 组成的 \(n \times n\) 的方阵。

方阵内只有一个闭合圈,圈内至少有一个 \(0\)

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #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

提示

对于 \(100\%\) 的数据,\(1 \le n \le 30\)

问题分析

本题很明显是一个搜索问题,解决搜索问题常用的有两种方法BFS和DFS,如果使用DFS会发现它会花费很多时间回溯,因为我们在搜索时只需要标记我们需要的位置即可,并不需要考虑标记的顺序,所以本题我还是更偏向使用BFS
我们只需要从圈外的一个点出发,标记圈外所有0即可,所以我们需要一个固定是在圈外的点,在原图中好像没有这个点,我们可以在圈外再开一圈0即可
代码

#include<iostream>
#include<queue>
using namespace std;
int d[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
int a[50][50]; //多开一点准没错
int n;
queue<pair<int, int > >que;
void bfs(int x, int y) {
	que.push(pair<int, int>(x, y));
	while (!que.empty()) {
		pair<int, int>t = que.front();
		que.pop();
		a[t.first][t.second] = 2;
		for (int i = 0; i < 4; i++) {
			//搜索四个方向
			int nx = t.first + d[i][0], ny = t.second + d[i][1];
            //别出界,且保证该点没有搜过,感觉访问数组会更慢些,所以放在了后面
			if ( nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= n + 1 && a[nx][ny] == 0 &&) {
				que.push(pair<int, int>(nx, ny));
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	//从外附边界开始搜索
	bfs(0, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << 2 - a[i][j]<<' '; //这个空格欸~~
		}
		//别忘记每行之后要换行
		cout << endl;
	}
	return 0;
}
From:https://www.cnblogs.com/oQAQo/p/18424178
本文地址: http://www.shuzixingkong.net/article/2184
0评论
提交 加载更多评论
其他文章 Python 潮流周刊#70:微软 Excel 中的 Python 正式发布!(摘要)
本周刊由 Python猫 出品,精心筛选国内外的 250+ 信息源,为你挑选最值得分享的文章、教程、开源项目、软件工具、播客和视频、热门话题等内容。愿景:帮助所有读者精进 Python 技术,并增长职业和副业的收入。 分享了 12 篇文章,12 个开源项目,2 则音视频,全文 2000 字。 以下是
Python 潮流周刊#70:微软 Excel 中的 Python 正式发布!(摘要)
以太坊Rollup方案之 arbitrum(2)
这篇博客主要介绍了Arbitrum验证节点的架构及其工作原理,重点讨论了验证节点的功能、AVM(Arbitrum虚拟机)的状态机结构、操作码及数据结构的细节,并深入解释了交互式证明的分割协议和单步证明的实现机制。通过图示,作者详细说明了验证节点如何通过二分协议来证明某个区块的正确性,并在必要时提交单
以太坊Rollup方案之 arbitrum(2) 以太坊Rollup方案之 arbitrum(2) 以太坊Rollup方案之 arbitrum(2)
Wpf使用NLog将日志输出到LogViewer
1 LogViewer LogViewer是通过UDP传输的高性能实时log查看器。 具有一下特性: 通过UDP读取日志 通过文件导入日志 导出日志到一个文件中 排序、过滤(日志树,日志等级)和查找 突出显示搜索文本 从UPD接收日志时忽略IP地址列表 多接收器支持 多种颜色主题 项目地址:http
Wpf使用NLog将日志输出到LogViewer
一,初始 MyBatis-Plus
一,初始 MyBatis-Plus @目录一,初始 MyBatis-Plus1. MyBatis-Plus 的概述2. 入门配置第一个 MyBatis-Plus 案例3. 补充说明:3.1 通用 Mapper 接口介绍3.1.1 Mapper 接口的 “增删改查”3.1.1.1 查询所有记录3.1.
一,初始 MyBatis-Plus 一,初始 MyBatis-Plus 一,初始 MyBatis-Plus
适用于 VitePress 的公告插件开发实记
开发了一个适用于 VitePress 站点的公告插件 vitepress-plugin-announcement
适用于 VitePress 的公告插件开发实记 适用于 VitePress 的公告插件开发实记 适用于 VitePress 的公告插件开发实记
Maven 使用方法
Maven Maven是一个项目管理工具,它包含了一个项目对象模型(POM:Project Object Model),其表现于一个XML文件(pom.xml),其中包含了项目的基本学习,依赖关系,插件配置,构建路径等等 为什么使用Maven 导入第三方jar包更便捷:之前我们在使用第三方框架时我们
Maven 使用方法 Maven 使用方法 Maven 使用方法
数字产品护照 (DPP) 解决方案:利用 Blazor 和区块链实现产品全生命周期追踪
数字产品护照 (DPP) 解决方案:利用 Blazor 和区块链实现产品全生命周期追踪 随着全球对可持续发展和产品透明度的关注日益增加,企业需要一种可靠的方法来跟踪和管理产品生命周期中的关键数据。我们的数字产品护照(Digital Product Passport,DPP)系统正是为此而生,提供了一
数字产品护照 (DPP) 解决方案:利用 Blazor 和区块链实现产品全生命周期追踪 数字产品护照 (DPP) 解决方案:利用 Blazor 和区块链实现产品全生命周期追踪 数字产品护照 (DPP) 解决方案:利用 Blazor 和区块链实现产品全生命周期追踪
Qt表格入门
这篇博客文章深入探讨了Qt表格处理的基础知识与实践技巧。主要内容包括:使用QTableWidget和QTableView展示数据,通过QStyledItemDelegate和QSortFilterProxyModel实现数据代理、过滤与排序功能。文章还附有详细的代码示例,指导读者如何在Qt中创建并个
Qt表格入门 Qt表格入门 Qt表格入门