长草问题详解：从暴力到优雅

问题理解

我们先来看一下这个问题到底在说什么：

小明有一块空地，被分成了n行m列的小格子。有些格子种了草（用’g’表示），有些还是空地（用’.’表示）。每个月，草会向四个方向（上、下、左、右）扩展到相邻的空地上。我们需要计算k个月后，整个空地的状态是什么样的。

这就像是在模拟草的生长过程：每个月，所有的草同时向外蔓延一格。

第一版代码的问题

我们先来看一下你的第一版代码，分析其中存在的问题：

cpp

#include <iostream>
using namespace std;

int main()
{
    char g[1005][1005];
    int m = 0, n = 0,k=0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> g[i][j];
        }
        cout<<endl;
    }
    cin >> k;
    for (int t = 0; t < k; t++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                for (int x = i - 1; x <= i + 1; x++)
                {
                    for (int y = j - 1; y <= j + 1; y++)
                    {
                        // 判断(x,y)是否在原数组的有效下标范围内
                        if (x >= 0 && x < n && y >= 0 && y < m && g[i][j] == 'g')
                        {
                            g[i - 1][j] = 'g';
                            g[i][j - 1] = 'g';
                            g[i][j + 1] = 'g';
                            g[i + 1][j] = 'g';
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << g[i][j];
        }
        cout<<endl;
    }
    return 0;
}

主要问题分析

实时修改问题：在遍历数组的同时修改数组内容，这会导致当月新长出的草在同一个月内继续扩散，而题目要求是所有草同时扩散。
冗余循环：使用了四层循环（t, i, j, x, y），其中x和y的循环是多余的，因为我们只需要检查四个方向。
边界处理问题：在设置g[i-1][j] = 'g'时没有检查边界，当i=0时，i-1=-1会导致数组越界。
效率问题：这样的实现时间复杂度很高，对于n=1000, m=1000, k=1000的情况，几乎不可能在合理时间内运行完成。

优化后的最终代码

你的修改非常到位，解决了第一版代码中的所有问题。我们来详细分析一下优化后的代码：

cpp

#include <iostream>
#include <cstring> // 用于memcpy
using namespace std;

// 上下左右四个方向的偏移量（简化扩展逻辑）
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

char g[1005][1005];
char temp[1005][1005];

int main()
{
    int m = 0, n = 0,k=0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> g[i];// 一行读取，比逐个读g[i][j]更简洁高效
    }
    cin >> k;
    for (int t = 0; t < k; t++)
    {
        // 步骤1：复制当前状态到临时数组（避免实时修改影响遍历）
        memcpy(temp, g, sizeof(g));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] == 'g')
                {
                    // 遍历上下左右四个方向（移除冗余的x/y循环）
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = i + dx[d]; // 新行坐标
                        int ny = j + dy[d]; // 新列坐标

                        // 关键：判断新坐标是否在有效范围内
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                        {
                            // 标记临时数组中该位置为草（原数组暂不修改）
                            temp[nx][ny] = 'g';
                        }
                    }
                 }
            }
        }
        // 步骤3：将临时数组的状态同步回原数组，完成当月扩展
        memcpy(g, temp, sizeof(g));
    }
    for (int i = 0; i < n; i++)
    {
        cout << g[i] << endl; // 直接输出整行，更简洁
    }
    return 0;
}

关键优化点详解

1. 使用临时数组保存状态

cpp

// 步骤1：复制当前状态到临时数组（避免实时修改影响遍历）
memcpy(temp, g, sizeof(g));

这是解决实时修改问题的关键。我们先把当前的状态复制到一个临时数组中，然后在临时数组上进行修改，这样就不会影响到原数组的遍历。

2. 使用方向数组简化代码

cpp

// 上下左右四个方向的偏移量（简化扩展逻辑）
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

方向数组是一种非常常见的技巧，可以大大简化代码。我们用两个数组分别表示x和y方向的偏移量，这样就可以用一个循环来处理四个方向。

3. 正确的边界检查

cpp

// 关键：判断新坐标是否在有效范围内
if (nx >= 0 && nx < n && ny >= 0 && ny < m)

在修改数组之前，我们先检查新坐标是否在有效范围内，这样就避免了数组越界的问题。

4. 高效的输入输出

cpp

cin >> g[i];// 一行读取，比逐个读g[i][j]更简洁高效

和

cpp

cout << g[i] << endl; // 直接输出整行，更简洁

这样的输入输出方式比逐个字符读写要高效得多，尤其是在处理大数组时。

算法复杂度分析

我们来分析一下这个算法的时间复杂度：

初始化：O(n*m)
每个月的模拟：O(nm4) = O(n*m)
k个月的总时间：O(knm)

对于n=1000, m=1000, k=1000的情况，总操作次数是10^9，这在实际运行中可能会超时。不过对于大多数编程题来说，这样的复杂度已经足够了。

进一步优化的思路

如果要处理更大的数据，我们可以使用广度优先搜索（BFS）的方法，这样可以将时间复杂度降低到O(n*m)，而不需要乘以k。

BFS优化思路

首先，我们找到所有初始的草的位置，将它们加入队列，并记录它们的生长时间为0。
然后，我们使用BFS的方式，依次处理队列中的每个位置，将它们的四个方向的空地标记为草，并记录它们的生长时间为当前时间+1。
当生长时间超过k时，停止扩展。

这样，我们只需要遍历整个数组一次，而不需要模拟k个月的生长过程。

BFS优化的具体实现

cpp

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

// 上下左右四个方向的偏移量
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

char g[1005][1005];
int time[1005][1005]; // 记录每个位置长草的时间

int main()
{
    int n, m, k;
    cin >> n >> m;
    
    queue<pair<int, int>> q;
    memset(time, -1, sizeof(time)); // 初始化时间为-1，表示未长草
    
    for (int i = 0; i < n; i++)
    {
        cin >> g[i];
        for (int j = 0; j < m; j++)
        {
            if (g[i][j] == 'g')
            {
                q.push({i, j});
                time[i][j] = 0; // 初始草的生长时间为0
            }
        }
    }
    
    cin >> k;
    
    // BFS过程
    while (!q.empty())
    {
        auto curr = q.front();
        q.pop();
        
        int x = curr.first;
        int y = curr.second;
        
        // 如果当前位置的生长时间已经等于k，不需要继续扩展
        if (time[x][y] >= k)
            continue;
        
        // 遍历四个方向
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            // 检查新坐标是否在有效范围内，并且未长草
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && time[nx][ny] == -1)
            {
                time[nx][ny] = time[x][y] + 1;
                g[nx][ny] = 'g';
                q.push({nx, ny});
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++)
    {
        cout << g[i] << endl;
    }
    
    return 0;
}

BFS优化的优势

时间复杂度更低：O(nm)，而不是O(kn*m)
更适合大数据：对于k很大的情况，比如k=10000，BFS方法仍然可以在O(n*m)的时间内完成
内存效率更高：不需要使用临时数组

总结

通过这个问题，我们学习了：

如何模拟扩散过程
如何避免实时修改数组的问题
如何使用方向数组简化代码
如何正确处理边界条件
如何提高输入输出效率
如何使用BFS优化算法

你的优化过程非常典型，从暴力遍历到使用临时数组，再到使用方向数组简化代码，这是一个非常好的学习过程。希望这篇文章能帮助你更好地理解这个问题和解决方案。