[201512-3]ccf-csp——画图-阿南达文事网

[201512-3]ccf-csp——画图

题目内容

输入格式
第1行有三个整数m, n和q。m和n分别表示画布的宽度和高度，以字符为单位。q表示画图操作的个数。
第2行至第q + 1行，每行是以下两种形式之一：

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

画布的左下角是坐标为 (0, 0) 的位置，向右为x坐标增大的方向，向上为y坐标增大的方向。这q个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .（小数点）。

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

输入示例1

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

输出示例1

输入示例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

评测用例规模与约定
所有的评测用例满足：2 ≤ m, n ≤ 100，0 ≤ q ≤ 100，0 ≤ x < m（x表示输入数据中所有位置的x坐标），0 ≤ y < n（y表示输入数据中所有位置的y坐标）

解题思路
看完题目之后容易发现，实际上的操作只有两种，所以对应每种操作分别写一个函数就行了。

首先是画线函数：

题目中说明了保证画的线一定是直线，不会是斜线，所以我们只需要考虑两种情况：x相同的画竖线情况，与y相同的画横线的情况。
获取起始点到终点的坐标，然后遍历画图就行了，但是这里有两个坑：

给出的x2或y2不保证一定比x1或y1大，所以这里需要人为判断一下。
画线的时候如果此时位置已经是‘ + ’了，不能修改。

然后是填色部分：

实际上填色部分就是普通的遍历，显然我们有bfs和dfs两种选择，这两种选择的中止判定都是一样的：

撞到了边界
要画的目标的颜色已经是当前的c了
撞到了画的线：‘ - ’ ‘ | ’ ‘ + ’

以下给出AC的代码，我把bfs和dfs的都写了。
实践是检验真理的唯一标准，这道题里，dfs不管是时间还是空间，都远胜于bfs…bfs甚至超时了，看官可自行取舍。

#include <iostream>
#include <vector>
#include <queue>using namespace std;//东北西南偏移值
const int offx[4] = { 1,0,-1,0 };
const int offy[4] = { 0,1,0,-1 };int m, n, op;//宽度，高度和操作的个数char map[101][101];//map[x][y]void DrawLine(int x1, int y1, int x2, int y2)
{if (x1 == x2)//画竖线{if (y2 < y1)//保证y2更大{int temp = y1;y1 = y2;y2 = temp;}for (int y = y1; y <= y2; y++){if (map[x1][y] == '+') continue;if (map[x1][y] == '-'){map[x1][y] = '+';}else{map[x1][y] = '|';}}}else if (y1 == y2){if (x2 < x1){int temp = x1;x1 = x2;x2 = temp;}for (int x = x1; x <= x2; x++){if (map[x][y1] == '+') continue;if (map[x][y1] == '|'){map[x][y1] = '+';}else{map[x][y1] = '-';}}}
}//这个结构体只给bfs使用
struct Point
{int x, y;Point(int x, int y) :x(x), y(y) {}
};void BfsFill(int x,int y,char c)
{Point s(x, y);queue<Point>q;q.push(s);while (!q.empty()){Point cur = q.front();q.pop();int tx = cur.x;int ty = cur.y;map[tx][ty] = c;for (int i = 0; i <= 3; i++){//下一个点int nx = tx + offx[i];int ny = ty + offy[i];//到达边界if (nx < 0 || nx >= m || ny <= 0 || ny >= n) continue;//撞到了线或者已经是该字符了if (map[nx][ny] == c ||map[nx][ny] == '-' ||map[nx][ny] == '|' ||map[nx][ny] == '+') continue;q.push(Point(nx, ny));}}
}void DfsFill(int x, int y, char c)
{//撞了边界if (x < 0 || x >= m || y < 0 || y >= n) return;//已经是此字符if (map[x][y] == c) return;if (map[x][y] != '-' && map[x][y] != '|' && map[x][y] != '+'){map[x][y] = c;for (int i = 0; i <= 3; i++){DfsFill(x + offx[i], y + offy[i], c);}}
}int main()
{ios::sync_with_stdio(false);cin >> m >> n >> op;//实际上map[m][i]和map[i][n]是边界，这里没有图for(int i=0;i<n;i++)for (int j = 0; j < m; j++){map[j][i] = '.';}int opnum, x1, y1, x2, y2;char tc;for (int i = 0; i < op; i++){cin >> opnum;if (opnum == 0){cin >> x1 >> y1 >> x2 >> y2;DrawLine(x1, y1, x2, y2);}else if (opnum == 1){cin >> x1 >> y1 >> tc;//BfsFill(x1, y1, tc);DfsFill(x1, y1, tc);}}//上下颠倒过来输出，因为题目中说了左下角为(0,0)//而个人理解里的数组是左上角为(0,0)//不同的人对数组的理解可能不一样for (int i = n - 1; i >= 0; i--){for (int j = 0; j < m; j++){cout << map[j][i];}cout << endl;}return 0;
}

[201512-3]ccf-csp——画图