画图

GitHub跳转原题关系图Canvas 关系图返回列表

按操作模拟水平线、竖直线与四连通填充，最后按纵坐标倒序输出画布。

OJ: shumeng

题目 ID: CSP201512C

难度:普及-

标签:模拟BFS二维数组

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 画线
    2. 填充
    3. 输出
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

在宽度为 mm、高度为 nn 的字符画布上依次执行 qq 个操作：

  • 0 x1 y1 x2 y2：画一条水平或竖直线段，用 - 或 | 表示；若与另一方向的线段相交，交点改成 +；
  • 1 x y c：从 (x,y)(x,y) 开始四连通填充字符 c，遇到线段（-、|、+）或画布边缘停止。

画布左下角坐标为 (0,0)(0,0)，xx 向右增大、yy 向上增大，初始全是 .。输出最终画布，每行 mm 个字符。

思路

画布用二维数组 board[y][x] 保存，注意下标与坐标的方向对应。

画线

  • 水平线段（y1=y2y_1 = y_2）：沿 xx 逐格写入 -；某格原本是 | 则改为 +。
  • 竖直线段（x1=x2x_1 = x_2）：沿 yy 逐格写入 |；某格原本是 - 则改为 +。

换一种写法：水平写入 - 的条件是“当前不是竖线”，竖线同理，二者交叉处自然得到 +。

填充

从起点做四连通 BFS。可到达的条件：坐标在画布内、未被访问过、当前格子不是线段（-、|、+）。每访问一个格子就涂上目标颜色。

输出

坐标 yy 向上增长，因此输出时要让行号从 n−1n-1 递减到 00，才能得到题目要求的“上方行在前”。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 23:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int m, n;             // 画布宽度与高度（以字符为单位）
char board[MAXN][MAXN]; // board[y][x] 保存画布，初始全为 '.'

// 在 (x1,y1) 到 (x2,y2) 之间画水平或竖直线段。
// 遇到另一方向的线段时改为 '+'.
void draw_line(int x1, int y1, int x2, int y2) {
    if (y1 == y2) { // 水平线段，用 '-'
        if (x1 > x2) swap(x1, x2);
        for (int x = x1; x <= x2; x++) {
            if (board[y1][x] == '|') board[y1][x] = '+';
            else board[y1][x] = '-';
        }
    } else { // 竖直线段，用 '|'
        if (y1 > y2) swap(y1, y2);
        for (int y = y1; y <= y2; y++) {
            if (board[y][x1] == '-') board[y][x1] = '+';
            else board[y][x1] = '|';
        }
    }
}

// 从 (x, y) 四连通填充 color；线段（- | +）是填充边界。
void flood_fill(int x, int y, char color) {
    int visited[MAXN][MAXN] = {};
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    queue<pair<int, int> > cells;
    cells.push(make_pair(x, y));
    visited[y][x] = 1;
    while (!cells.empty()) {
        pair<int, int> current = cells.front();
        cells.pop();
        int cx = current.first, cy = current.second;
        board[cy][cx] = color;
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[ny][nx]) continue;
            if (board[ny][nx] == '-' || board[ny][nx] == '|' || board[ny][nx] == '+') continue;
            visited[ny][nx] = 1;
            cells.push(make_pair(nx, ny));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) board[y][x] = '.';
    }

    int q;
    cin >> q;
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 0) { // 画线
            int x2, y2;
            cin >> x2 >> y2;
            draw_line(x, y, x2, y2);
        } else { // 填充
            char color;
            cin >> color;
            flood_fill(x, y, color);
        }
    }

    // 画布左下角是 (0,0)，y 向上增长，因此从高到低输出每一行。
    for (int y = n - 1; y >= 0; y--) {
        for (int x = 0; x < m; x++) cout << board[y][x];
        cout << '\n';
    }
    return 0;
}

复杂度

  • 时间：每次填充最多访问整个画布，共 qq 次操作，O(qmn)O(qmn)。
  • 空间：画布数组与访问标记，O(mn)O(mn)。

总结

绘图与填充严格按输入顺序执行；线段是填充的边界，而先前填充的字母不是边界。坐标映射（y 向上增长、输出倒序）是本题最容易出错的地方，先在草图上确认下标方向再编码。