AcWing 3224. 画图 (BFS,Flood Fill,坐标变换)

用 ASCII 字符来画图是一件有趣的事情,并形成了一门被称为 ASCII Art 的艺术。

例如,下图是用 ASCII 字符画出来的 CSPRO 字样。

  ..____.____..____..____...___..
  ./.___/.___||.._.\|.._.\./._.\.
  |.|...\___.\|.|_).|.|_).|.|.|.|
  |.|___.___).|..__/|.._.<|.|_|.|
  .\____|____/|_|...|_|.\_\\___/.

本题要求编程实现一个用 ASCII 字符来画图的程序,支持以下两种操作:

  • 画线:给出两个端点的坐标,画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符 -来画,竖直线段用字符 |来画。如果一条水平线段和一条竖直线段在某个位置相交,则相交位置用字符 +代替。
  • 填充:给出填充的起始位置坐标和需要填充的字符,从起始位置开始,用该字符填充相邻位置,直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 4 4 个方向,如下图所示,字符 @只和 4 4 4 个字符 *相邻。
  .*.
  *@*
  .*.

输入格式
1 1 1 行有三个整数 m , n m,n m,n q q q m m m n n n 分别表示画布的宽度和高度,以字符为单位。 q q q 表示画图操作的个数。

2 2 2 行至第 q + 1 q+1 q+1 行,每行是以下两种形式之一:

0 x1 y1 x2 y2:表示画线段的操作, ( x 1 , y 1 ) (x1,y1) (x1,y1) ( x 2 , y 2 ) (x2,y2) (x2,y2) 分别是线段的两端,满足要么 x 1 = x 2 x1=x2 x1=x2 y 1 ≠ y 2 y1≠y2 y1=y2,要么 y 1 = y 2 y1=y2 y1=y2 x 1 ≠ x 2 x1≠x2 x1=x2
1 x y c:表示填充操作, ( x , y ) (x,y) (x,y) 是起始位置,保证不会落在任何已有的线段上; c c c 为填充字符,是大小写字母。画布的左下角是坐标为 ( 0 , 0 ) (0,0) (0,0) 的位置,向右为 x x x 坐标增大的方向,向上为 y y y 坐标增大的方向。

q q q 个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .(小数点)。

输出格式
输出有 n n n 行,每行 m m m 个字符,表示依次执行这 q q q 个操作后得到的画图结果。

数据范围
2 ≤ m , n ≤ 100 , 2≤m,n≤100, 2m,n100
0 ≤ q ≤ 100 , 0≤q≤100, 0q100
0 ≤ x < m 0≤x<m 0x<m x x x 表示输入数据中所有位置的 x x x 坐标),
0 ≤ y < n 0≤y<n 0y<n y y y 表示输入数据中所有位置的 y y y 坐标)。

输入样例1:

4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A

输出样例1:

AAAA
A--A

输入样例2:

16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C

输出样例2:

................
...+--------+...
...|CCCCCCCC|...
...|CC+-----+...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC+-----+...
...|CCCCCCCC|...
...+--------+...
................

一道Flood Fill题,但是本题难点在于对于坐标的处理,题目要求的坐标是数学坐标,而编程语言中的坐标并不与其相同,主要区别如下:
在这里插入图片描述
那么这里就分化出了两种做法:直接想办法把二维数组的坐标表示转化为按照题目给出的数学坐标或是把不改变二维数组坐标转而改变读入的坐标与输出的坐标。

当然二者中后者更为简单,本人采用前者频频错误,且本题难以Debug。
故采用后者。
首先在读入中,如果把 x x x y y y 对应的坐标交换读入,那么就会获得类似于这样的坐标存储:
在这里插入图片描述
处于题目要求我们输出时要让他像是数学坐标一样,那么就可以让 x x x 轴倒着输出。

#include<iostream>
#include<queue>
using namespace std;
const int N = 110;
#define pii pair<int,int>
#define x first
#define y second
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

char g[N][N];
int n, m, q;

int main() {
	cin >> m >> n >> q;

	for (int i = 0; i < n; i++) {		//先初始化
		for (int j = 0; j < m; j++) {
			g[i][j] = '.';
		}
	}

	while (q--) {
		int op;cin >> op;

		if (op == 0) {	//划线操作
			int x1, y1, x2, y2; cin >> y1 >> x1 >> y2 >> x2;//倒着读x,y
			if (x1 == x2) {
				for (int i = min(y1, y2); i <= max(y1, y2); i++) {
					if (g[x1][i] == '|' || g[x1][i] == '+')g[x1][i] = '+';	//重点注意'+'也要判断
					else g[x1][i] = '-';
				}
			}
			else {
				for (int i = min(x1, x2); i <= max(x1, x2); i++) {
					if (g[i][y1] == '-' || g[i][y1] == '+')g[i][y1] = '+';
					else g[i][y1] = '|';
				}
			}
		}
		else {
			int x1, y1; char c; cin >> y1 >> x1 >> c;

			auto bfs = [&]() {	//Flood Fill过程
				queue<pii>q;
				q.push({ x1,y1 });
				g[x1][y1] = c;

				while (q.size()) {
					auto t = q.front();
					q.pop();

					for (int i = 0; i < 4; i++) {
						int xx = t.x + dx[i], yy = t.y + dy[i];

						if (xx >= 0 && xx < n && yy >= 0 && yy < m) {
							if (g[xx][yy] == '+' || g[xx][yy] == '-' || g[xx][yy] == '|')continue;
							if (g[xx][yy] == c)continue;

							g[xx][yy] = c;
							q.push({ xx,yy });
						}
					}
				}
				};

			bfs();
		}
	}

	for (int i = n - 1; i >= 0; i--) {	//由于题目要求原因最后要倒着输出
		for (int j = 0; j < m; j++) {
			cout << g[i][j];
		}
		puts("");
	}

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/478957.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring之@Qualifier注解

场景重现 当我们注入的依赖存在多个候选者,我们得使用一些方法来筛选出唯一候选者,否则就会抛出异常 demo演示 创建接口Car,以及两个实现其接口的bean public interface Car { }Component public class RedCar implements Car { }Component public class WhiteCar implemen…

【python】python葡萄酒数据集—分类建模与分析(源码+数据集)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…

Git原理及使用

1、Git初识 Git是一种版本控制器: 对于同一份文件,做多次改动,Git会记录每一次改动前后的文件。 通俗的讲就是⼀个可以记录⼯程的每⼀次改动和版本迭代的⼀个管理系统,同时也⽅便多⼈协同作业。 注意: Git其实只能跟踪⽂本⽂件的改动,⽐如TXT⽂件,⽹⻚,所有的程序代码…

matlab实现机器学习svm

一、目的和要求 1.编程实现SVM训练函数和预测函数&#xff1b; 2.绘制线性和非线性边界&#xff1b; 3.编写线性核函数 二、算法 1.线性svm&#xff1a; 分离超平面&#xff1a;wxb0&#xff0c;对于线性可分的数据集来说&#xff0c;这样的超平面有无穷多个&#xff08;…

汽车ECU的虚拟化技术(五) -- 对MCU虚拟化实现难点的思考

目录 1.概述 2.虚拟化软件的难点 2.1 虚拟化中的中断处理 2.2 虚拟ECU的通信 3.小结 1.概述 在上面文章里汽车ECU的虚拟化技术(四) -- 对MCU虚拟化实现难点的思考-CSDN博客&#xff0c;解了OEM面临新的电子电气架构下的集成难点&#xff0c;引入了hypervisor以及VM调度机制…

VMD + CEEMDAN 二次分解,CNN-Transformer预测模型

往期精彩内容&#xff1a; 时序预测&#xff1a;LSTM、ARIMA、Holt-Winters、SARIMA模型的分析与比较-CSDN博客 风速预测&#xff08;一&#xff09;数据集介绍和预处理-CSDN博客 风速预测&#xff08;二&#xff09;基于Pytorch的EMD-LSTM模型-CSDN博客 风速预测&#xff…

研华工控机610L学习笔记1:基本了解与认识

今日开始学习一些工控机的基本知识&#xff1a; 目录 目录 1、工控机介绍&#xff1a; 2、研华610L说明书参数了解&#xff1a; 3、基本结构了解&#xff1a; 前面板&#xff1a; 后窗&#xff1a; 4.RS232串口&#xff1a; ​编辑 5、工控机分类&#xff1a; 6、工控上…

深度学习pytorch——激活函数损失函数(持续更新)

论生物神经元与神经网络中的神经元联系——为什么使用激活函数&#xff1f; 我们将生物体中的神经元与神经网络中的神经元共同分析。从下图可以看出神经网络中的神经元与生物体中的神经元有很多相似之处&#xff0c;由于只有刺激达到一定的程度人体才可以感受到刺激&#xff0c…

一、SpringBoot基础搭建

本教程主要给初学SpringBoot的开发者&#xff0c;通过idea搭建单体服务提供手把手教学例程&#xff0c;主要目的在于理解环境的搭建&#xff0c;以及maven模块之间的整合与调用 源码&#xff1a;jun/learn-springboot 以商城项目为搭建例子&#xff0c;首先计划建1个父模块&…

微服务高级篇(三):分布式缓存+Redis集群

文章目录 一、单点Redis的问题及解决方案二、Redis持久化2.1 单机安装Redis2.2 RDB持久化2.3 AOF持久化2.4 RDB和AOF对比 三、Redis主从3.1 搭建Redis主从架构3.1.1 集群结构3.1.2 准备实例和配置3.1.3 启动3.1.4 开启主从关系3.1.5 测试 3.2 数据同步3.2.1 全量同步【建立连接…

【嵌入式——QT】QWT应用

【嵌入式——QT】QWT应用 概述步骤一步骤二步骤三代码声明代码实现图示 概述 QWT&#xff0c;全称Qt Widgets for Technical Applications&#xff0c;是一个基于Qt开发的第三方库。它主要为具有技术背景的程序提供GUI组件和一组实用类&#xff0c;用于生成各种统计图。QWT的主…

【JDBC编程】Java连接MySQL的五个步骤

目录 JDBC编程 1.JDBC的使用 2.数据库连接Connection 3.Statement对象 4.ResultSet对象 JDBC编程 JDBC编程运用了MySQL提供的 Java 的驱动包 mysql-connector-java &#xff0c;需要基于 Java 操作 MySQL 即需要该驱动包。同样的&#xff0c; 要基于 Java 操作 Oracle 数据库…

【文本输入框】显示输入文本的字数,并且限制输入字数不能超过***个字符

需求 实现一个输入框显示文本的字数&#xff0c;并且设置字数限制&#xff0c;当文本中没有内容或字符串长度超出限制&#xff0c;则不能点击确定按钮。 <div class"input-content"><div class"pt-2 rounded-tl-xl rounded-tr-xl bg-blue-100"&…

vue3+threejs新手从零开发卡牌游戏(十):创建己方战域

首先在game目录下创建site文件夹&#xff0c;用来存放战域相关代码&#xff1a; 这里思考下如何创建战域&#xff0c;我的想法是添加一个平面&#xff0c;将己方战域和对方战域都添加进这个平面中&#xff0c;所以首先我们先添加一个战域plane&#xff0c;site/index.vue代码如…

C是用什么语言写出来的?

C是用什么语言写出来的? C语言的起源和发展是一个迭代过程&#xff1a; 1. 最初的C语言编译器的开发始于对B语言的改进。B语言是由Ken Thompson设计的&#xff0c;它是基于BCPL语言简化而来的。在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「 C语言的…

2024.3.20 使用maven打包jar文件和保存到本地仓库

2024.3.20 使用maven打包jar文件和保存到本地仓库 使用maven可以很方便地打包jar文件和导入jar文件&#xff0c;同时还可以将该文件保存在本地仓库重复调用。 使用maven打包jar文件和保存到本地仓库 package打包文件。 install导入本地仓库。 使用maven导入jar文件 点击“…

基于GIS、RS、VORS模型、CCDM模型、geodetecto、GWR模型集成的生态系统健康的耦合协调分析技术

集成多源数据&#xff0c;依托ArcGIS Pro和R语言环境&#xff0c;采用“活力-组织力-恢复力-贡献力”&#xff08;VORS&#xff09;模型定量测算生态系统健康指数&#xff08;EHI&#xff09;&#xff1b;如何从经济城镇化&#xff08;GDPD&#xff09;、人口城镇化&#xff08…

【算法杂货铺】分治

目录 &#x1f308;前言&#x1f308; &#x1f4c1; 快速排序 &#x1f4c2;75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; &#x1f4c2; 912. 排序数组 - 力扣&#xff08;LeetCode&#xff09; &#x1f4c2; 215. 数组中的第K个最大元素 - 力扣&#xff08;Lee…

以RISC-V架构的CLIC中断机制讲解:中断咬尾、中断抢占、中断晚到

1、中断的相关属性 中断所属特权模式&#xff08;M模式 > S模式 > U模式&#xff09;中断等级&#xff1a;决定是否能够抢占当前的中断中断优先级&#xff1a;影响中断的仲裁&#xff0c;优先级高时优先被响应中断编号&#xff1a;区分中断&#xff0c;影响中断的仲裁 …

操作系统面经-什么是操作系统?

通过以下四点可以概括操作系统到底是什么&#xff1a; 操作系统&#xff08;Operating System&#xff0c;简称 OS&#xff09;是管理计算机硬件与软件资源的程序&#xff0c;是计算机的基石。操作系统本质上是一个运行在计算机上的软件程序 &#xff0c;主要用于管理计算机硬…