P4919 绘图工具（基础）

解题思路

第一步，理解题意。 有一个3行5列的大写字母矩阵。给定一个坐标(x,y)和一个字母c，要把所有与(x,y)这个格子里的字母相同的、并且能通过上下左右或对角线连通的字母，全部改成c。连通块就是8个方向都算相邻的一组相同字母。

第二步，找到起始字母。 先读入矩阵和坐标x、y、要改成的字母c。题目里的x、y从1开始数，我们在程序里减1变成从0开始。起始位置的字母用src表示，接下来要找到所有和src相同的、与(x,y)连通的格子。

第三步，深度优先搜索染色。 写一个递归函数fill(x,y)：如果当前位置越界，或者字母不是src，就直接返回；否则把当前位置的字母改成c，然后对它的8个邻居（上、下、左、右、左上、右上、左下、右下）分别递归调用fill。这样所有与起点连通的src字母都会被改成c。

第四步，注意特殊情况。 如果c和src相同，那么什么都不用改，直接输出原矩阵就行。这也能避免递归无限循环，因为改完字母没变化，访问标记不起作用。代码里加了一句判断：只有src不等于c时才调用fill。

第五步，输出结果。 3行每行5个字母，连续输出即可，字母之间不用空格。例如样例中(2,2)是字母A，8个方向上连通的A都被改成E，输出EEEEA、WEBBB、BEECC，和样例一致。

参考代码

// 绘图工具：8方向连通块染色，把(x,y)所在连通块的全部字母改成c
#include <iostream>
using namespace std;
char g[5][6];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void fill(int x, int y, char src, char c) {
    if (x < 0 || x >= 3 || y < 0 || y >= 5) return;
    if (g[x][y] != src) return;
    g[x][y] = c;
    for (int d = 0; d < 8; d++) fill(x + dx[d], y + dy[d], src, c);
}
int main() {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 5; j++) cin >> g[i][j];
    int x, y;
    char c;
    cin >> x >> y >> c;
    x--; y--; // 输入的坐标从1开始，转成从0开始
    char src = g[x][y];
    if (src != c) fill(x, y, src, c); // 相同字母时无需修改，也避免死循环
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 5; j++) cout << g[i][j];
        cout << endl;
    }
    return 0;
}

复杂度分析

矩阵只有3行5列共15个格子，深度优先搜索每个格子最多被访问一次，每个格子又访问8个邻居，所以时间复杂度是O(15×8)，非常小。递归深度最多15层，不会爆栈。空间上只存了一个3×6的字符数组，空间复杂度O(1)。