草坪杂草清除问题高效程序实现及现有Java代码性能优化咨询

阿华AIGC实验室

2026-4-28

优化草坪杂草清除算法的性能问题

原代码的性能瓶颈分析

你的原代码采用了循环迭代的方式，不断遍历整个矩阵来决定是否将当前单元格的杂草通过踩踏转移到其他位置。但这种方法的问题在于：每一轮迭代都要扫描所有n*m个单元格，而且可能需要多轮迭代才能让所有单元格的状态稳定下来。当n和m的规模较大时，这种全矩阵遍历的重复操作会导致时间复杂度急剧上升，最坏情况下可能达到O(k*(n*m))（k为迭代轮数），性能自然不理想。

另外，代码里还有个小笔误：(j+1)%n应该是(j+1)%m——j是列索引，对应的模数值应该是列数m，否则当m≠n时会出现索引错误。

优化思路：直接计算每株杂草的最优清除代价

我们可以换个角度思考：每一株初始杂草，最终要么在当前单元格直接拔除，要么经过若干次踩踏操作后，转移到某个（或某些）单元格再拔除。而清除一株杂草的最小代价，本质上是在"直接拔除"和"踩踏后清除衍生杂草"之间做选择。

我们可以定义dp[i][j]为清除单元格(i,j)中1株杂草所需的最小能量，那么对于每个单元格，有以下关系：

dp[i][j] = min( E[i][j], dp[(i+1)%n][j] + dp[i][(j+1)%m] )

这里的逻辑是：要么直接花E[i][j]拔除，要么踩踏它（代价是后续两个单元格清除衍生杂草的最小代价之和）。由于矩阵是循环的，这是一个带环的动态规划问题，但我们可以用队列驱动的增量更新来高效计算所有单元格的最优dp值，避免全矩阵的重复遍历。

优化后的Java代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class WeedRemovalOptimized {
    static class Pair {
        int i, j;
        Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        // 读取拔除能量矩阵
        int[][] E = new int[n][m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                E[i][j] = scanner.nextInt();
            }
        }

        // 初始化dp矩阵：初始值为直接拔除的代价
        long[][] dp = new long[n][m];
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] inQueue = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = E[i][j];
                queue.add(new Pair(i, j));
                inQueue[i][j] = true;
            }
        }

        // 用SPFA风格的队列更新dp值，只处理需要更新的单元格
        while (!queue.isEmpty()) {
            Pair curr = queue.poll();
            int i = curr.i;
            int j = curr.j;
            inQueue[i][j] = false;

            // 更新前驱单元格：(i-1)%n, j
            int prevI = (i - 1 + n) % n;
            int prevJ = j;
            long newVal = Math.min(dp[prevI][prevJ], dp[i][j] + dp[prevI][(prevJ + 1) % m]);
            if (newVal < dp[prevI][prevJ]) {
                dp[prevI][prevJ] = newVal;
                if (!inQueue[prevI][prevJ]) {
                    queue.add(new Pair(prevI, prevJ));
                    inQueue[prevI][prevJ] = true;
                }
            }

            // 更新前驱单元格：i, (j-1)%m
            prevI = i;
            prevJ = (j - 1 + m) % m;
            newVal = Math.min(dp[prevI][prevJ], dp[(prevI + 1) % n][prevJ] + dp[i][j]);
            if (newVal < dp[prevI][prevJ]) {
                dp[prevI][prevJ] = newVal;
                if (!inQueue[prevI][prevJ]) {
                    queue.add(new Pair(prevI, prevJ));
                    inQueue[prevI][prevJ] = true;
                }
            }
        }

        // 计算总能量：根据初始杂草分布累加代价
        long[][] weedCount = new long[n][m];
        for (int t = 0; t < k; t++) {
            int i = scanner.nextInt();
            int j = scanner.nextInt();
            weedCount[i][j]++;
        }

        long totalEnergy = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                totalEnergy += weedCount[i][j] * dp[i][j];
            }
        }

        System.out.println(totalEnergy);
        scanner.close();
    }
}