首页 > 其他分享 >填涂颜色

填涂颜色

时间:2024-05-22 10:53:28浏览次数:28  
标签:填涂 le 颜色 int 闭合 nx maxn 方阵

传送锚点:https://www.luogu.com.cn/problem/P1162血色先锋队

题目描述

由数字 \(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\)。

思路

此题是想将把被1包围的0全都转换为2,将未访问过的点,且该点为0,转换为2,引入最外圈去讨论

code

#include<iostream>
using namespace std;
const int maxn = 35;
int n;
int g[maxn][maxn];//地图
typedef pair<int, int> PII;
PII q[maxn * maxn];
bool st[maxn][maxn];//是否访问过这个点
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
void bfs(int x,int y) {
	q[0] = { x,y };
	int head = 0, tail = 0;//此时已有点入队
	while (head <= tail) {
		auto t = q[head ++];//出队
		st[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];
			if (nx < 0 || nx>n + 1 || ny<0 || ny>n + 1) continue;
			if (st[nx][ny]) continue;
			if (g[nx][ny] == 1) continue;//若此点为1,就不用向外搜索 
			st[nx][ny] = true;
			q[++tail] = { nx,ny };
		}
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	bfs(0, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!st[i][j] && g[i][j] == 0) {//地图中为0的位置未被访问过
				g[i][j] = 2;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << g[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

标签:填涂,le,颜色,int,闭合,nx,maxn,方阵
From: https://www.cnblogs.com/6Luffy6/p/18205740

相关文章

  • .bashrc 给文件夹添加颜色
    .bashrc给文件夹添加颜色#~/.bashrc:executedbybash(1)fornon-loginshells.#see/usr/share/doc/bash/examples/startup-files(inthepackagebash-doc)#forexamples#Ifnotrunninginteractively,don'tdoanything[-z"$PS1"]&&r......
  • POI 重叠、并列柱状图(条形图),显示数据,自定义颜色
    1、pom.xml<dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxml</artifactId><version>4.1.2</version></dependency><dependency><groupId>org.apache.poi</groupId><artifac......
  • 【图像处理】使用matplotlib库显示灰度图像为自定义颜色(2)
    在下面的代码中,facies_img的值只有[0,1,2]表明图像是灰度图像。通过下面的代码可以让图像显示为彩色图像importmatplotlib.pyplotaspltimportmatplotlib.colorsasmcolorsfromPILimportImageimportosimportrandomimportnumpyasnp#路径设置data_dir='data......
  • 网页布局------悬浮在input框上时旁别按钮边框颜色也会发生变化
    input边框和按钮放在同一个div下,使用hover可以设置悬浮在input边框时的颜色变化,而需要设置按钮边框的颜色变化则需要使用"+"来添加 页面结构<divclass="nav-search"><inputtype="search"placeholder="小米11"class="nav-search-inpu......
  • QTableView设置单元格颜色未生效的问题
    问题:1voidMainWindow::on_tableview_clicked(constQModelIndex&index)2{3item=newQStandardItem("clicked");4//ui->plant_table->data()5item->setData(QBrush(Qt::red),Qt::BackgroundRole);//.setColor(Qt::red)......
  • pyqt5设计图片背景和颜色
        tianqi.qrc 根据大小重新 <RCC><qresourceprefix="media"><file>天气.jpg</file><file>音乐.jpg</file><file>map.png</file><file>车.png</file></qresource></RCC>......
  • 好看的文字颜色
    海蓝 #70DB93巧克力色 #5C3317蓝紫色 #9F5F9F黄铜色 #B5A642青铜色 #8C78532号青铜色 #A67D3D士官服蓝色 #5F9F9F冷铜色 #D98719铜色 #B87333珊瑚红 #FF7F00紫蓝色 #42426F深绿 #2F4F2F深铜绿色 #4A766E深橄榄绿 #4F4F2F深兰花色 #9932CD深紫色 #8......
  • 【LeetCode 1648】销售价值减少的颜色球
    题目描述原题链接:LeetCode.1648销售价值减少的颜色球解题思路题意很容易理解,就是每次挑剩余同色球数量最大的颜色卖得到最大价值,总共卖orders个球的最大总价值;最快速直观暴力的解法是按照同色球数量排序,每次取数量最大值累加到总价值中并且将数量减一后重新排序,重复or......
  • 获取给定区域内的符合颜色值的第一个和最后一个坐标
    fromPILimportImageGrabimportpyautoguiimporttimeimportpyperclipimportnumpydef获取给定区域内的符合颜色值的第一个和最后一个坐标(left_x:int,left_y:int,right_x:int,right_y:int,color_r:int,color_g:int,color_b:int)->list:'''注意,本函数直接截取......
  • png图片更换前景颜色
    png图片更换前景颜色#regionpng图片转换前景色///<summary>///获取原图的像素点颜色值,修改颜色值///</summary>///<paramname="bmp">原图</param>///<returns>修改原图的像素点颜色值之后的图</returns>publicstaticBitmapSetBitmapColor(Bitmapbmp,Color......