P4892 林地修补（基础）

解题思路

第一步，读懂题目。 有一片 n×n 的林地，每个格子里是一种树木（用小写字母表示）。专家选中一个起始位置，并给出一个新的树木品种 c。我们要把"从起始位置出发、能通过相邻格子连过去的、所有和起始位置树木品种相同的格子"，全部换成新品种 c。注意这里相邻是指八个方向（上下左右加四个斜角）。

第二步，像传话一样扩散。 从起点 (x,y) 出发，它自己是 old 这种树。我们看看它周围八个格子，凡是有树正好也是 old 的，就把它也换成 c，再继续看新换格子的周围……这就是"洪水填充"（flood fill），就像往水池里倒墨水，墨水会沿着连通的水路一直扩散。

第三步，用深搜实现。 写一个函数 dfs(x,y)：先把当前格子换成 c，数量加一，然后循环八个方向，如果新位置在林地范围内、而且字母还是 old，就递归进去。八个方向同样用 dx、dy 两个数组表示。

具体例子： 样例里起点 (1,1) 是 w，把所有连在一起的 w 都换成 p，一共换了 8 个格子。输出时先输出换好的整个林地，最后再单独输出数量 8。

边界情况： 起点自己也要换成 c 并计数。题目保证新品种 c 和原来的树不一样，所以不用担心换完又换回去。换过的格子字母变成 c 后，自然就不会再被当成 old 处理了。

参考代码

// 林地修补：把起点可达(八个方向)的相同字母格子全部换成新字母
#include <iostream>
using namespace std;

int n, sx, sy, cnt;
char g[12][12], c, old; // g存林地, cnt记录修改的格子数
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 从(x,y)沿八方向替换相同字母
void dfs(int x, int y) {
    g[x][y] = c; cnt++;
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && g[nx][ny] == old)
            dfs(nx, ny);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    cin >> sx >> sy >> c; // 起点行列与新字母
    old = g[sx][sy];      // 记录起点原来的字母
    dfs(sx, sy);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << g[i][j];
        cout << endl;
    }
    cout << cnt << endl; // 输出修改的格子数量
    return 0;
}

复杂度分析

每个格子最多被访问一次，所以时间复杂度是 O(n²)。n 最大是 10，一共 100 个格子，非常快。空间上需要存 n×n 的林地，是 O(n²)。