刷了leetcode8月20日每日一题,你不想写一个扫雷游戏吗?

748 阅读6分钟

8月20号这天,慢悠悠的来到工位打开电脑打开leetcode,看看每日一题,如果不是困难难度的题,我会尝试着刷一下这天的题,很好,这天是一个中 等难度的题。

题还是比较简单的,大概就是求扫雷点击某一次之后面板的结果。 题目链接:leetcode-cn.com/problems/mi…

刷完这道题心里就有一个想法,写一个扫雷游戏试试吧? 一不做二不休,趁着周末来了写了一个粗糙的扫雷游戏,然后顺手写一篇实现总结。

本次分享文章主要涉及到的点为:

  1. 生成随机雷分布的洗牌算法
  2. 深度优先搜索计算每次操作后面板的结果。

代码已经上传到github:github.com/Chechengyi/…

1 用二维数组模拟地雷及其操作结果

看到扫雷的这个界面长啥样子我相信首先第一能想到的就是使用二维数组去表示这个界面。 以图中的扫雷举例子 这应该是一个 10 * 10 的二维数组。 我这里的表示参考了leetcode的表现方式。

  • E : 代表一个未挖出的方块
  • M: 代表一个未挖出的地雷

先去只管这两种状态去生成一个地图(扫雷的界面,等下都这么称呼)。比如,规定 简单难度的 10 * 10 的数组中的地雷个数为10个,先写一个方法生成地图,并把雷布进去:

	export type Label = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
	export type GridStatus = 'M' | 'E' | 'B' | 'X' | Label
	export type Map = Array<Array<GridStatus>>
    // 先不管除了 E 和 M 的其他状态,后面会讲到
    function getMaps(row: number, col: number, rayNums: number): Map {
    	let maps: Map = []
  		let currentRayNums = 0;
        for (let i =0; i < row; i++) {
      		maps[i] = []
      		for (let j = 0; j < col; j++) {
              if (currentRayNums < rayNums) {
                  maps[i].push('M')
                  currentRayNums++
              } else {
                  maps[i].push('E')
              }
      		}
    	}
    }

这样生成的二维数组渲染出来就是:

刚说的,我们用 E代表未挖出的方块,M代表未挖出的地雷。 可以看到有个问题,就是这样我们生成的地雷就全部在第一行。 这是肯定不行的,所以接下来要使用洗牌算法去随机分布地雷。

2 使用洗牌算法随机地雷位置

在实现二维数组的乱序之前,先考虑一下要给一个一维数组乱序,该怎么做?

比如一个数组:[1,2,3,4,5,6,7,8,9,10]。现在要给这个数组乱序,在学习洗牌算法之前,我的思路是:在创建一个一维数组arr,然后生成一个随机数字0~9 取数组下标,取出这个下标对应的数字放到arr的首位,然后继续这个操作。

但是这样做有个问题,生成的随机数组是不可控的,有可能会出现我生成了两次下标3 的随机数。这时我需要在用一个map去记录已经生成过的随机数字,如果这个随机数已经生成过了就不能用了需要在在重新生成一个。 这样的问题是随着生成的下标越来越多。生成的随机数重复的概率会越来越大,那么会在生成下标这个地方尝试很多次。

然后来看看洗牌算法是怎么做的:以之前的数组为例子,在我看来其思想就是,首先在下标 08之间取出一个数字与下标9 位置处数字交换。 然后下标9位置处的数字就是“洗” 过了的,然后再在下标07之间取出一个数字与下标8处交换,一直重复这个步骤。 代码:

	var arr = [1,2,3,4,5,6,7,8,9,10]
	function shuffle(arr){
		var index = arr.length
		while(index>1){
			let num = parseInt(Math.random()*index--)
				swap(num, index, arr)
			}
		}

	function swap(i,j,arr){
		var mid = arr[i]
		arr[i] = arr[j]
		arr[j] = mid
	}
	shuffle(arr)
	console.log(arr)

这样就实现了一维数组的乱序。

二维数组是同样的道理,比如一个二维数组有m行列,要实现这个二维数组的乱序。要做的事情就是在 1m 行 和 ***1n-1*** 列中找出确定一个坐标,将其位置与 第 m行 第 n 列处的位置交换,然后在 1m 行 和 ***1n-2*** 列 中确定一个坐标,将其位置与地 m行 第n-1 列处位置交换,重复这个步骤。 代码就不贴了,暂时实现不了的话可以去仓库里看有现成的代码。

实现了二维的乱序之后效果如图下所示。

3 标记每一个格子的状态

上文已经提到了,用E去表示一个未翻开的格子的情况,用M去表示一个未翻开的地雷。 现在我们将翻开的格子的状态补上。玩过扫雷游戏的朋友都知道,当你翻开一个格子的时候有可能运气不佳刚好翻到了一个地雷,这时你的游戏就结束了。也有可能翻开了一个格子,显示的是一个数字,这个数字代表的是以当前位置为一个九宫格的中心,外面一圈存在几个地雷。 还有一种情况就是点开一个格子翻开了一大片,这种情况也是我以前沉迷扫雷游戏无法自拔的一个原因。 这种情况是怎么产生的呢? 比如我当前点击了一个格子,以它为中心所处的九宫格之内如果没有地雷的话,就会对九宫格内的格子在模拟一次点击操作。

ok,接下来参照leetcode的表示定义好状态

  • X: 表示翻开了一个地雷
  • B:表示翻开的这个格子周围没有地雷
  • 0~8:表示翻开的这个格子周围有几个地雷

如果理解不了这些状态定义,建议玩几把扫雷感受一下,相信可以很快明白。

4 实现扫雷游戏算法

接下来这块儿算法实现应该就是扫雷游戏最核心的部分了。

首先分析一下这个算法到底要做一个什么事情,实际上就是当用户点击某一个格子之后,要按照游戏规则将操作后的结果计算出来。那么首先这个算法需要用到的参数就有:表示地雷图的二维数组、用户点击行的位置(row)、用户点击的列的位置(col)。

  1. 首先第一种情况也就是最简单的,用户点击到的格子刚好是一个地雷,那么很简单,将当前位置置为X。
  2. 用户点击到的位置不是地雷,那么此时首先要计算以此位置为中心的九宫格之内有多少个地雷,比如说有3个,那么就将当前位置置为3。 此时这里还有一种情况就是周围没有地雷,那么就要对周围一圈的格子模拟点击操作。

算法的实现比较简单,主要实现方式分为深度优先搜索和广度优先搜索两种。 有些东西可能越解释越不明白,我也自认描述能力比较差。 我直接贴上我的代码的实现方式写一点注释,感兴趣的可以去看看本道题的题解。

深度优先搜索:

var updateBoard = function(board, click) {

  // x, y 表示点击的位置  type=click 表示是点击操作 check代表是模拟点击的操作  
  function backTrack(x, y, type){
    // 限定范围,如果已经超出了二维数组的范围直接返回  
    if ( x < 0 || x==board.length ) return
    if (y < 0 || y==board[0].length) return

    // 当前的位置是地雷
    if ( board[x][y] == 'M' ) {
      // 当前位置是地雷且是一次点击操作,则置为X  然后返回  不再做计算
      if ( type == 'click' ){
        board[x][y] = 'X'
      }
      return
    }

    // 如果当前位置不为E,则之前这个位置已经点击过 直接返回 不再做计算
    if ( board[x][y] !== 'E' ) return

    let ret = computedNum(x, y)
    if (ret==0){
      // 如果周围的雷为0 置为B  
      board[x][y] = 'B'
    } else {
      board[x][y] = ret + ''
    }

    // 周围的雷为0 才需要对九宫格内的其他位置进行模拟操作
    if (board[x][y] !== 'B') return

    let startX = x-1
    let startY = y-1
    let endX = x+1
    let endY = y+1

    for ( var i=startX; i<=endX; i++ ) {
      for ( var j=startY; j<=endY; j++ ) {
        if ( i==x && j==y ) continue
        // 进行模拟操作
        backTrack(i, j, 'check')
      }
    }
  }

  // 计算以某个点为中心的周围雷的个数  
  function computedNum(x, y){
    let startX = x-1
    let startY = y-1
    let endX = x+1
    let endY = y+1
    let ret = 0
    for ( var i=startX; i<=endX; i++ ) {
      for ( var j=startY; j<=endY; j++ ) {
        if ( i==x && j==y ) continue
        if ( i < 0 || i==board.length ) continue
        if (j < 0 || j==board[0].length) continue
        if ( board[i][j] == 'M' ) ret++
      }
    }
    return ret
  }

  backTrack(click[0], click[1], 'click')
  return board
};

广度优先搜索:

var updateBoard = function(board, click) {
  // 用于存放需要执行点击操作的位置  
  var task = [click]
  // 表明当前操作是否真实点击操作,只有第一次是真实点击
  var isClick = true  
  while(task.length>0){
      // 取出需要操作的位置
      let current = task.pop()
      let x = current[0]
      let y = current[1]
      if ( board[x][y] === 'M' ) {
          if (isClick) board[x][y] = 'X'
          continue
      }
      if ( board[x][y] !== 'E' ) continue
      let ret = computedNum(x, y, board)
      if (ret==0){
      // 如果周围的雷为0 置为B  
        board[x][y] = 'B'
      } else {
        board[x][y] = ret + ''
      }
      if (board[x][y] !== 'B') continue

        let startX = x-1
        let startY = y-1
        let endX = x+1
        let endY = y+1

        for ( var i=startX; i<=endX; i++ ) {
        for ( var j=startY; j<=endY; j++ ) {
            if ( i==x && j==y ) continue
            if ( i < 0 || i==board.length ) continue
            if (j < 0 || j==board[0].length) continue
            // 将位置push进栈中
            task.push([i,j])
        }
        }
        isClick = false
    }
  return board
};

// 计算以某个点为中心的周围雷的个数  
  function computedNum(x, y, board){
    let startX = x-1
    let startY = y-1
    let endX = x+1
    let endY = y+1
    let ret = 0
    for ( var i=startX; i<=endX; i++ ) {
      for ( var j=startY; j<=endY; j++ ) {
        if ( i==x && j==y ) continue
        if ( i < 0 || i==board.length ) continue
        if (j < 0 || j==board[0].length) continue
        if ( board[i][j] == 'M' ) ret++
      }
    }
    return ret
  }

5 总结

至此完成一个扫雷游戏最核心的部分已经完成了,剩下的只是一些边边角角了,比如UI的呈现,比如扫雷标记地雷,判断游戏结果,不在多赘述了。感兴趣仓库有现成的代码: github.com/Chechengyi/… 。 如果文章中有什么不对的地方请大家指出,我的总结也是一个学习的过程。