Coursera普林斯顿课程扫雷Minesweeper程序提交超时问题求助

核心问题：地雷生成逻辑存在死循环风险，是超时的根本原因 #

• 坐标转换逻辑错误导致可分配地雷的格子数量不足
  你当前的随机坐标处理逻辑存在严重错误：生成的随机数r范围是0 ~ m*n-2，后续对q和rem的强制修正操作，直接把第m行、第n列的格子全部排除出了可放地雷的范围，实际可分配地雷的格子只有(m-1)*(n-1)个。当测试用例的k大于(m-1)*(n-1)时，循环永远无法达到num == k的终止条件，直接进入死循环导致超时。
  正确的坐标转换应该是：从0~m*n-1生成随机数r，直接计算q = r / n + 1，rem = r % n + 1，刚好覆盖所有1<=q<=m、1<=rem<=n的有效格子，不需要多余的修正。
• 拒绝采样在k接近总格子数时效率极低
  当k占总格子数比例很高时，随机生成的坐标大概率已经被标记为地雷，每次循环成功放置地雷的概率极低，循环次数会指数级上升，最终触发超时。

次要优化点：输出效率可提升 #

你当前每次输出单个单元格就调用一次System.out.print，频繁IO操作也会增加耗时，可以先拼接整行内容再一次性输出。

修复后的参考代码 #

public class Minesweeper {
    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);
        int k = Integer.parseInt(args[2]);
        boolean[][] minePositions = new boolean[m + 2][n + 2];
        int[][] grid = new int[m + 2][n + 2];
        int total = m * n;
        // 用洗牌算法生成地雷位置，无重复，效率稳定
        int[] cells = new int[total];
        for (int i = 0; i < total; i++) {
            cells[i] = i;
        }
        // 洗牌只需处理前k个元素即可满足需求
        for (int i = 0; i < k; i++) {
            int r = i + (int) (Math.random() * (total - i));
            int temp = cells[r];
            cells[r] = cells[i];
            cells[i] = temp;
            // 直接标记前k个为地雷
            int q = cells[i] / n + 1;
            int rem = cells[i] % n + 1;
            minePositions[q][rem] = true;
        }
        // 统计相邻地雷数
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (minePositions[i][j]) continue;
                int count = 0;
                for (int di = -1; di <= 1; di++) {
                    for (int dj = -1; dj <= 1; dj++) {
                        if (di == 0 && dj == 0) continue;
                        if (minePositions[i + di][j + dj]) count++;
                    }
                }
                grid[i][j] = count;
            }
        }
        // 批量输出减少IO次数
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (minePositions[i][j]) {
                    sb.append("*  ");
                } else {
                    sb.append(grid[i][j]).append("  ");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

内容的提问来源于stack exchange，提问作者Alinaswe klb