扫雷程序地雷随机分布异常：测试9失败与性能优化求助

一、解决地雷分布不均匀问题（测试9失败） #

你当前的随机地雷生成逻辑大概率是重复调用Math.random()生成坐标再去重的方式——这种方法会因坐标碰撞导致部分单元格被选中的概率偏低，甚至完全无法被选中，直接触发G-statistic测试失败。

最优的均匀分布生成方式是Fisher-Yates洗牌算法：将所有棋盘单元格的索引存入数组，打乱顺序后取前N个作为地雷位置，确保每个单元格被选中的概率完全相等。

实现代码 #

// 假设棋盘为rows行cols列，需要放置mineCount个地雷
int[] cellIndices = new int[rows * cols];
// 初始化所有单元格索引（0到rows*cols-1）
for (int i = 0; i < cellIndices.length; i++) {
    cellIndices[i] = i;
}

// Fisher-Yates洗牌：原地打乱数组，保证均匀分布
for (int i = cellIndices.length - 1; i > 0; i--) {
    // 生成0到i的随机索引（含i）
    int randomIdx = (int) (Math.random() * (i + 1));
    // 交换当前位置与随机位置的元素
    int temp = cellIndices[i];
    cellIndices[i] = cellIndices[randomIdx];
    cellIndices[randomIdx] = temp;
}

// 标记前mineCount个索引对应的单元格为地雷
for (int i = 0; i < mineCount; i++) {
    int idx = cellIndices[i];
    int row = idx / cols;
    int col = idx % cols;
    board[row][col] = '*'; // 用*标记地雷
}

这种方式完全避免了重复随机的碰撞问题，每个单元格被选为地雷的概率严格等于mineCount/(rows*cols)，可以轻松通过分布均匀性测试。

二、解决超时问题（测试10未完成） #

超时的核心原因是周边地雷计数逻辑效率低下——如果是事后遍历每个单元格，再逐个检查8个方向统计地雷数，时间复杂度会达到O(mn*8)，大棋盘下必然超时。

优化思路是埋地雷时同步更新周边计数：在标记地雷的同时，直接给周围8个方向的非地雷单元格的计数加1，一次遍历完成所有计数工作，时间复杂度降至O(mn + mineCount*8)。

实现代码 #

首先初始化棋盘所有非地雷单元格为'0'：

// 初始化棋盘
char[][] board = new char[rows][cols];
for (int i = 0; i < rows; i++) {
    Arrays.fill(board[i], '0');
}

然后在埋地雷的循环中同步更新周边计数（配合上面的洗牌代码）：

// 定义8个方向的偏移量（无需扩展网格，直接做边界检查）
int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1},
                      {0, -1},          {0, 1},
                      {1, -1},  {1, 0}, {1, 1}};

for (int i = 0; i < mineCount; i++) {
    int idx = cellIndices[i];
    int row = idx / cols;
    int col = idx % cols;
    board[row][col] = '*'; // 标记地雷

    // 遍历8个方向，更新周边单元格的地雷计数
    for (int[] dir : directions) {
        int newRow = row + dir[0];
        int newCol = col + dir[1];
        // 边界检查：确保坐标在棋盘范围内，且不是地雷
        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && board[newRow][newCol] != '*') {
            // 字符转整数加1，再转回字符
            board[newRow][newCol] = (char) (board[newRow][newCol] - '0' + 1 + '0');
        }
    }
}

这种方式省去了事后二次遍历统计的开销，大幅提升大棋盘下的运行效率，解决超时问题。

额外优化建议 #

如果棋盘规模极大，使用数组存储单元格索引比ArrayList更高效（避免自动扩容和装箱拆箱开销），上面的代码已经采用数组实现。另外，确保Math.random()的使用正确：(int)(Math.random() * range)可以生成0到range-1的均匀随机整数，洗牌时的randomIdx计算逻辑是正确的。

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