首页 > 代码库 > CCF 201512-3 画图 (DFS搜索+模拟)

CCF 201512-3 画图 (DFS搜索+模拟)

2024-08-12 15:28:04   217人阅读

问题描述
　　用 ASCII 字符来画图是一件有趣的事情，并形成了一门被称为 ASCII Art 的艺术。例如，下图是用 ASCII 字符画出来的 CSPRO 字样。
　　..____.____..____..____...___..
　　./.___/.___||.._.\|.._.\./._.\.
　　|.|...\___.\|.|_).|.|_).|.|.|.|
　　|.|___.___).|..__/|.._.<|.|_|.|
　　.\____|____/|_|...|_|.\_\\___/.
　　本题要求编程实现一个用 ASCII 字符来画图的程序，支持以下两种操作：
　　? 画线：给出两个端点的坐标，画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符 - 来画，竖直线段用字符 | 来画。如果一条水平线段和一条竖直线段在某个位置相交，则相交位置用字符 + 代替。
　　? 填充：给出填充的起始位置坐标和需要填充的字符，从起始位置开始，用该字符填充相邻位置，直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 个方向，如下图所示，字符 @ 只和 4 个字符 * 相邻。
　　.*.
　　*@*
　　.*.
输入格式
　　第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个操作后得到的画图结果。
样例输入
4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A
样例输出
AAAA
A--A
样例输入
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
样例输出
................
...+--------+...
...|CCCCCCCC|...
...|CC+-----+...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC+-----+...
...|CCCCCCCC|...
...+--------+...
................
评测用例规模与约定
　　所有的评测用例满足：2 ≤ m, n ≤ 100，0 ≤ q ≤ 100，0 ≤ x < m（x表示输入数据中所有位置的x坐标），0 ≤ y < n（y表示输入数据中所有位置的y坐标）。
 
析：这个题线段就是模拟，要么横着，要么竖着画，然后就是填充用的是DFS，就是深搜，把所有的能填充都填充上，我觉得坑就是有的+可能会覆盖。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const LL LNF = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 100 + 5;const int mod = 1e9 + 7;const int dr[] = {-1, 0, 1, 0};const int dc[] = {0, 1, 0, -1};const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){    return r >= 0 && r < n && c >= 0 && c < m;}char s[maxn][maxn];void dfs(int r, int c, char ch){    s[r][c] = ch;    for(int i = 0; i < 4; ++i){        int x = r + dr[i];        int y = c + dc[i];        if(!is_in(x, y) || s[x][y] == ch || s[x][y] == ‘+‘ || s[x][y] == ‘-‘ || s[x][y] == ‘|‘ )  continue;        dfs(x, y, ch);    }}void print(){    for(int i = n-1; i >= 0; --i){        for(int j = 0; j < m; ++j)            printf("%c", s[i][j]);        printf("\n");    }}int main(){    while(scanf("%d %d", &m, &n) == 2){        int q; scanf("%d", &q);        for(int i = 0; i < n; ++i)            for(int j = 0; j < m; ++j)                s[i][j] = ‘.‘;        int p, x, y, x1, x2, y1, y2;        char ch[5];        while(q--){            scanf("%d", &p);            if(p){               scanf("%d %d %s", &y, &x, ch);               dfs(x, y, ch[0]);            }            else{                scanf("%d %d %d %d", &y1, &x1, &y2, &x2);                if(x1 > x2) swap(x1, x2);                if(y1 > y2) swap(y1, y2);                if(x1 == x2)                    for(int i = y1; i <= y2; ++i)                        if(s[x1][i] == ‘|‘ || s[x1][i] == ‘+‘)  s[x1][i] = ‘+‘;                        else  s[x1][i] = ‘-‘;                else                    for(int i = x1; i <= x2; ++i)                        if(s[i][y1] == ‘-‘ || s[i][y1] == ‘+‘)  s[i][y1] = ‘+‘;                        else  s[i][y1] = ‘|‘;            }        }        print();    }    return 0;}

 

CCF 201512-3 画图 (DFS搜索+模拟)


联系
我们