AcWing 3224. 画图（BFS，Flood Fill，坐标变换）

本文主要是介绍AcWing 3224. 画图（BFS，Flood Fill，坐标变换），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

　　.*.*@*.*.

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

第 $2$ 行至第 $q + 1$ 行，每行是以下两种形式之一：

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

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

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

数据范围
$2 \leq m, n \leq 100 ，$
$0 \leq q \leq 100 ，$
$0 \leq x < m$ （ $x$ 表示输入数据中所有位置的 $x$ 坐标），
$0 \leq y < n$ （ $y$ 表示输入数据中所有位置的 $y$ 坐标）。

输入样例1：

输出样例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$ 和 $y$ 对应的坐标交换读入，那么就会获得类似于这样的坐标存储：
在这里插入图片描述
处于题目要求我们输出时要让他像是数学坐标一样，那么就可以让 $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，yif (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;
}