CSP201512-3 画图（C++实现）

题目

样例输入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|...
...+--------+...
................

思路

首先用char类型的二维数组存储画布。

题目需要实现两个功能：划线与填充。

划线：相对简单不多解释，但需要注意，横竖相接的格子需要改成'+'，且已经变成'+'的格子不能再被横线和竖线覆盖。

填充：填充可以使用dfs或者bfs，我采用了bfs的方法。因为要向上下左右四个方向进行填充，所以使用dx与dy来声明一个偏移量（可以方便地使用循环）。因为填充字符不能覆盖横线、竖线或者'+'，因此在遇到这些标志或者画布边界（或者已经经过的格子）时都不将其加入队列。

另外要注意从二维数组到输出画布的转化，并不是直接对应的。

代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

char bu[110][110];
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };
bool vis[110][110];

queue<pair<int, int> > q;
int m, n, k;

void func0(int x1, int y1, int x2, int y2)
{
	if (x1 == x2)
	{
		if (y1 > y2)
			swap(y1, y2);
		int num = y2 - y1;
		for (int i = 0; i <= num; i++)
		{
			if(bu[x1][y1 + i] == '-')//已经是横线
				bu[x1][y1 + i] = '+';//+
			else if (bu[x1 + i][y1] != '+')
				bu[x1][y1 + i] = '|';//竖线	
		}
	}
	else
	{
		if (x1 > x2)
			swap(x1, x2);
		int num = x2 - x1;
		for (int i = 0; i <= num; i++)
		{
			if (bu[x1 + i][y1] == '|')//已经是竖线
				bu[x1 + i][y1] = '+';//+
			else if(bu[x1 + i][y1] != '+')
				bu[x1 + i][y1] = '-';//横线
			
		}
	}
}

void func1(int x, int y, char c)
{
	memset(vis, 0, sizeof vis);
	pair<int, int> p1(x, y);
	q.push(p1);
	if (bu[x][y] != '-' && bu[x][y] != '|' && bu[x][y] != '+')
		bu[x][y] = c;
	vis[x][y] = 1;
	while (!q.empty())//bfs
	{
		pair<int, int> p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)//四个方向
		{
			int xx = p.first + dx[i];
			int yy = p.second + dy[i];
			if (vis[xx][yy] == 0 && xx >= 0 && xx < m && yy >= 0 && yy < n 
                            && bu[xx][yy] != '-' && bu[xx][yy] != '|' && bu[xx][yy] != '+')
			{
				pair<int, int> p2(xx, yy);
				q.push(p2);
				bu[xx][yy] = c;
				vis[xx][yy] = 1;
			}
		}
	}
}

int main() 
{
	memset(bu, '.', sizeof bu);
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++)
	{
		int op;
		cin >> op;
		if (op == 0)
		{
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			func0(x1, y1, x2, y2);
		}
		else 
		{
			int x, y;
			char c;
			cin >> x >> y >> c;
			func1(x, y, c);
		}
	}

	for (int j = n-1; j >= 0; j--)
	{
		for (int i = 0; i < m; i++)
			cout << bu[i][j];
		cout << endl;
	}
	system("Pause");
	return 0;
}