A81e5086ebcb70857e1a7d232877188f
扫雷与算法:如何随机化的布雷(一)

这是通过「扫雷与算法」小程序来讲解算法的第一章:如何随机化的进行布雷,主要介绍了三种不那么好的方法,希望通过这些不好的方法能让大家明白第二章要讲解的「洗牌算法」有多牛逼。

补充:「扫雷与算法」小程序会在写完后进行开源,发布在我的 GitHub 上面。

方法一

最想当然的方法就是随机的在二维区间寻找一个点布雷即可,代码如下:

for (var i = 0; i < mineNumber; i++) {
       var row = this.rangeRandom(0, this.rowCount - 1);
       var col = this.rangeRandom(0, this.colCount - 1);
       //使用数字 9 表示该区域有雷
       tmpMineMap[row][col] = 9;
 }

这种实现逻辑的一个弊端就是会在已经布雷的位置再度布雷,进而导致整个区域的布雷数量与要求不符合。

如上图所示,需要布雷的个数为 5 ,但在最后一次的随机布雷过程中只埋了 4 颗雷。

方法二

方法二是对方法一的改善:既然会重复埋雷,那么只需要再埋雷的过程中判断一下该位置是否已经埋雷即可。

  • 如果该位置是空的,那么则布雷,然后进行寻找新的位置布下下一颗雷
  • 如果该位置已经被安置了雷,那么就需要重新生成一个位置来安置

代码如下:

   for (var i = 0; i < mineNumber; i++) {
      //通过死循环来实现不停的寻找,直到安置好雷
      while (true) {
        var row = this.rangeRandom(0, this.rowCount - 1);
        var col = this.rangeRandom(0, this.colCount - 1);
        //用数字 9 表示该区域有雷,如果该位置没有布雷,那么则放置
        if (tmpMineMap[row][col] != 9) {
           tmpMineMap[row][col] = 9;
           //跳出循环
           break;
        }
      }
    }

使用效果如下:

top Created with Sketch.