CCF认证2015123-画图

显然，这道题需要设计两类操作，一个是画线，另一个是填充。画线的时候要注意画竖线时要先验证待画位置是否已经为横线或是交叉线（我之前就是因为忽略了交叉的情况致使最后的结果一直都是90分TT），画横线的时候也是如此考虑。填充的时候可以使用BFS或DFS算法来进行操作。由于题目的要求，还需要一个额外的标记数组来存放哪些位置已经被画线从而控制填充操作的范围。

本题并不算难，但是有许多细节需要注意。例如题目对坐标的规定与数组的下标并不是完全对应的关系，画线的时候容易忽略遇到交叉线的情况，填充操作时验证标记情况可能会出现越界。

本文使用的是BFS算法来实现的填充操作。如果对DFS算法实现填充操作感兴趣的话可以移步至：日沉云起：CCF认证201512-3画图。

具体代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void drawLine(vector<vector<char>> &mp, vector<vector<int>> &frame) //画线操作
{
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	getchar();
	if(x1 == x2) //画竖线
	{
		int x = x1;
		int begin = min(y1, y2);
		int end = y1 + y2 - begin;
		for(int i = begin; i <= end; i++)
		{
			if(mp[i][x] == '-' || mp[i][x] == '+') mp[i][x] = '+';
			else mp[i][x] = '|';
			frame[i][x] = 1;
		}
	}
	else //画横线
	{
		int y = y1;
		int begin = min(x1, x2);
		int end = x1 + x2 - begin;
		for(int i = begin; i <= end; i++)
		{
			if(mp[y][i] == '|' || mp[y][i] == '+') mp[y][i] = '+';
			else mp[y][i] = '-';
			frame[y][i] = 1;
		}
	}
}

void drawFill(vector<vector<char>> &mp, vector<vector<int>> &frame) //填充操作
{
	int x, y;
	cin >> x >> y;
	char c;
	cin >> c;
	getchar();
	int dx[] = {0, 0, -1, 1};
	int dy[] = {-1, 1, 0, 0};
	vector<vector<int>> mark; //本次填充操作要用到的临时标记数组
	mark = frame;
	queue<pair<int,int>> q; //存放填充位置坐标的队列
	q.push({y, x});
	int n = mp.size();
	int m = mp[0].size();
	while(!q.empty()) //BFS
	{
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		//为了不报错，最好先检验越界再检验标记
		if(cy < 0 || cy >= n || cx < 0 || cx >= m || mark[cy][cx]) continue;
		mp[cy][cx] = c;
		mark[cy][cx] = 1;
		for(int i = 0; i < 4; i++) //将相邻位置坐标放入队列中
			q.push({cy + dy[i], cx + dx[i]});
	}
}

int main()
{
	//FILE *stream;
	//freopen_s(&stream, "data.txt", "r", stdin);

	int m, n, q;
	cin >> m >> n >> q;
	getchar();
	vector<vector<char>> mp; //存放画布
	vector<vector<int>> frame; //存放画线后留下的痕迹用以填充操作
	for(int i = 0; i < n; i++)
	{
		mp.push_back(vector<char>(m, '.'));
		frame.push_back(vector<int>(m, 0));
	}
	for(int i = 0; i < q; i++)
	{
		if(getchar() == '0') drawLine(mp, frame);
		else drawFill(mp, frame);
	}
	for(int i = n - 1; i >= 0; i--) //注意题目对坐标的要求与数组的下标是存在不同的
	{
		for(int j = 0; j < m; j++)
		{
			cout << mp[i][j];
		}
		cout << endl;
	}

	//fclose(stream);

	return 0;
}

CCF认证2015123-画图

相关推荐