生成一个扫雷矩阵

警钟

当被考到输出一个扫雷矩阵时，才发现自己的代码写得多么差：忽略边界条件、死循环，考虑不周到，健壮性极差！写下这篇文章给自己敲个警钟吧，也对等概率随机抽取问题做一个总结

扫雷矩阵要求

m * n 的矩阵中有k个雷，输出一个矩阵满足：

1. 等概率随机生成地雷
2. 非地雷的格子的值是包围它的8个格子中含有地雷的总数

一开始的代码

被要求用C语言写生成矩阵的函数，但我竟然忘记了C语言中的函数调用和数组初始化，还把判断条件写在了for循环中，导致循环都进不去，太糟糕了，不好意思贴上来，下面的代码是改动后的。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int Count(int i, int j, int **a, int m, int n) {
    int cnt = 0;
    for (int p=i-1;p<=i+1;p++) {
        for (int q=j-1;q<=j+1;q++) {
            if (p < 0 || p >= n || q < 0 || q >= m) {
                continue;
            }
            if (a[p][q] == -1) {
                cnt++;
            }
        }
    }
    return cnt;
}

int** GenerateMatrix(int m, int n, int k, int **a) {
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            a[i][j] = 0;
        }
    }
    srand((unsigned)time(NULL)); 
    while(k > 0) {
        int i, j;
        i = rand() % m;
        j = rand() % n;
        if (a[i][j] == -1) {
            continue;
        }
        a[i][j] = -1;
        k--;
    }
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if (a[i][j] != -1) {
                a[i][j] = Count(i, j, a, m, n);
            }
        }
    }
    return a;
}

int main(){
    int m, n ,k;
    m = 10;
    n = 9;
    k = 5;
    int **a = (int **)malloc(m*sizeof(int *));
     for(int i=0;i<m;i++){
         a[i] = (int *)malloc(n*sizeof(int));
    }
    a = GenerateMatrix(m,n,k,a);
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            printf("%5d ", a[i][j]);
        }
        printf("\n");
    }
    for (int i=0;i<n;i++){
        free(a[i]);
    }
    free(a);
    return 0;
}

代码中的问题：

1. 当 k>m*n 时出现死循环
2. 生成地雷位置的过程用下面总结，觉得自己是在搞笑

   闭着眼睛乱猜整数，直到偶然碰上正确的那个为止”（《编程珠玑（续）》，13.1节）

改善思路

• 为了避免重复取到已变成雷的位置，需要把已生成的地雷位置移除，可借用洗牌算法，将二维数组当成一维数组看待，每个位置存储一个矩阵格子的坐标，但只抽取k个坐标即可，每个坐标抽取的概率为1/（m*n）
• 限制 k 的最大值，当 k > m*n 时返回空数组

改进后用go写的

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    m, n, k := 9, 10, 5
    matrix := GenerateMatrix(m, n, k)

    for i, _ := range matrix {
        for j, _ := range matrix[i] {
            fmt.Printf("%5d ", matrix[i][j])
        }
        fmt.Println()
    }
}

/**
*    m: 矩阵行数
*    n: 矩阵列数
*    k: 雷的个数
*    m, n为正整数, k为非负整数
**/
func GenerateMatrix(m, n, k int) [][]int {
    if k > m*n {
        return [][]int{}
    }
    last := m * n
    matrix := make([][]int, m)
    minePos := make([]int, k)
    for k, _ := range matrix {
        matrix[k] = make([]int, n)
    }
    // 初始化矩阵
    for i, _ := range matrix {
        for j, _ := range matrix[i] {
            matrix[i][j] = i*n + j // 把该二维数组看成一维数组，矩阵每格存储一维数组中的下标，该下标用以计算二维数组中的横纵坐标，方便后续等概率随机生成雷
        }
    }
    // 洗牌算法，利用二维数组等概率随机生成雷的位置，减少内存开销
    rand.Seed(time.Now().Unix())
    for k > 0 && last >= 1 {
        pos := rand.Intn(last) // 生成[0, last)的随机值；注意：Intn函数的参数要大于0
        posi, posj := getPosiAndPosj(pos, m, n)
        lasti, lastj := getPosiAndPosj(last-1, m, n)
        matrix[posi][posj], matrix[lasti][lastj] = matrix[lasti][lastj], matrix[posi][posj]
        last--
        k--
    }
    // 将雷的位置转移到另一数组存放，避免将雷的位置标记为-1时覆盖/丢失其它雷的位置。
    for i := last; i < m*n && k < m*n; i++ {
        posi, posj := getPosiAndPosj(i, m, n)
        minePos[k] = matrix[posi][posj]
        k++
    }
    // 标记矩阵中雷的位置，值置为-1
    for _, v := range minePos {
        posi, posj := getPosiAndPosj(v, m, n)
        matrix[posi][posj] = -1
    }
    // 遍历矩阵，统计雷的个数
    for i, _ := range matrix {
        for j, _ := range matrix[i] {
            if matrix[i][j] != -1 {
                matrix[i][j] = Count(i, j, matrix)
            }
        }
    }
    return matrix
}

//////////////////////////
// 二维数组a[i][j]和一维数组a[p]的坐标对应关系， 下标都从0开始
// i = p / 列数
// j = p - i * 列数
////////////////////////

func getPosiAndPosj(pos, m, n int) (posi, posj int) {
    if pos < 0 || pos > m*n {
        fmt.Println("坐标转换出现错误！")
        return
    }
    posi = pos / n
    posj = pos - posi*n
    return
}

// 周围8个格子是雷的个数
func Count(i, j int, matrix [][]int) int {
    cnt := 0
    for p := i - 1; p <= i+1; p++ {
        for q := j - 1; q <= j+1; q++ {
            if p < 0 || p >= len(matrix) || q < 0 || q >= len(matrix[0]) {
                continue
            }
            if matrix[p][q] == -1 {
                cnt++
            }
        }
    }
    return cnt
}

若还有问题，请各位指出来！！谢谢了！！

等概率随机选取扩展

上面矩阵大小由 m*n 固定，雷的个数也不太大，但如果矩阵大小不知或非常大，该如何等概率随机生成雷的位置呢？
参考Reservoir Sampling - 蓄水池抽样这篇博文，总结的很好。介绍了 如何从未知大小样本中随机抽取 1 个数，如何从未知大小样本中随机抽取 k 个数。
在这里我解释一下下面这段伪代码：从未知大小或非常大的样本空间中，如何等概率随机选取 k 个数

Init : a reservoir with the size： k

for i= k+1 to N
    M=random(1, i);
    // 从1到i中随机选取的数在前k个数中的概率为k/i，即第i个数（大于k）选取概率为k/i
    if( M < k)
        SWAP the Mth value and ith value
end for 

在选取过程中，第 i 个数是否被选取，只和 i 之后的数有关联，在选择 i 之前的数时，i 还没出现。

概率问题扩展

参考这篇文章概率问题总结，比较全面，面试可能会遇到的概率问题都有

参考链接

1. 从未知大小的n个数中取m个数，使各数被取出的概率相等
2. 等概率无重复的从n个数中选取m个数
3. Reservoir Sampling - 蓄水池抽样
4. 概率问题总结

本作品采用《CC 协议》，转载必须注明作者和本文链接