golang刷leetcode 技巧（70）扫雷游戏

golangLeetcode

发布于 2022-08-02 18:55:16

7120

文章被收录于专栏：golang算法架构leetcode技术phpgolang算法架构leetcode技术php

《扫雷》是一款大众类的益智小游戏，于1992年发行。游戏目标是在最短的时间内根据点击格子出现的数字找出所有非雷格子，同时避免踩雷，踩到一个雷即全盘皆输。

可以对应建模成一个二维数组

1,'M' 代表一个未挖出的地雷

2,'E' 代表一个未挖出的空方块

3,'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块

4,数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻

5,'X' 则表示一个已挖出的地雷。

给定一个代表游戏板的二维字符矩阵。

现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

1,如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。

2,如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。

3,如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。

4,如果在此次点击中，若无更多方块可被揭露，则返回面板。

示例 1：

输入:

[['E', 'E', 'E', 'E', 'E'],

['E', 'E', 'M', 'E', 'E'],

['E', 'E', 'E', 'E', 'E'],

['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],

['B', '1', 'M', '1', 'B'],

['B', '1', '1', '1', 'B'],

['B', 'B', 'B', 'B', 'B']]

解释:

示例 2：

输入:

[['B', '1', 'E', '1', 'B'],

['B', '1', 'M', '1', 'B'],

['B', '1', '1', '1', 'B'],

['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

输出:

[['B', '1', 'E', '1', 'B'],

['B', '1', 'X', '1', 'B'],

['B', '1', '1', '1', 'B'],

['B', 'B', 'B', 'B', 'B']]

解释:

注意：

输入矩阵的宽和高的范围为 [1,50]。

点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。

输入面板不会是游戏结束的状态（即有地雷已被挖出）。

简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。

解题思路：

1，对于扫雷，迷宫，等问题基本解决思路就是深度优先遍历，或者广度优先遍历

2，深度优先遍历一般是递归比较简单

3，本题其实是在深度优先遍历基础上加上一些游戏规则

4，如果点到雷，直接标记雷，返回

5，如果点击到雷相邻区域，标记周围雷的数量返回

6，如果点到和雷不相邻的区域，进行递归处理

7，递归结束边界条件，没有空的未访问区域可以遍历（遇到雷，或者遍历过的区域都结束）

8，遍历过程中重复5～7

代码实现

var byteArr =[]byte{'1','2','3','4','5','6','7','8'}
func updateBoard(board [][]byte, click []int) [][]byte {
   if board[click[0]][click[1]]=='M'{
        board[click[0]][click[1]]='X'
       return board
   }
   c:=count(board,click)
   if c>0{
       board[click[0]][click[1]]=byteArr[c-1]
       return board
   }
   board[click[0]][click[1]]='B'
   return updateBoardRecusive(board, click[0],click[1])
}
func  updateBoardRecusive(board [][]byte,x,y int)[][]byte {
        for _,i:=range([]int{-1,0,1}){
            for _,j:=range([]int{-1,0,1}){
                if i==0 && j==0{
                    continue
                }

                if empty(board,x+i,y+j){
                    c:=count(board,[]int{x+i,y+j})
                    //fmt.Println(c,x+i,y+j)
                    if c>0{
                        board[x+i][y+j]=byteArr[c-1]
                    }else{
                        board[x+i][y+j]='B'
                        board=updateBoardRecusive(board,x+i,y+j)
                    }
                } 
            }
        }

        return board  
}

func empty(board [][]byte,x,y int) bool{
    if x<0 ||x>=len(board){
        return false
    }
    if y<0 || y>=len(board[0]){
        return false
    }
    return board[x][y]=='E'//|| board[x][y]=='M'
}

func count(board [][]byte, click []int)int{
    x:=click[0]
    y:=click[1]

    sum:=0
    for _,i:=range([]int{-1,0,1}){
        for _,j:=range([]int{-1,0,1}){
            if i==0 && j==0{
                continue
            }
            sum+=hit(board,x+i,y+j)
        }
    }
    return sum
}

func hit(board [][]byte, x,y int)int{
    if x<0 ||x>=len(board){
        return 0
    }
    if y<0 || y>=len(board[0]){
        return 0
    }
    if board[x][y]=='M'{
        return 1
    }
    return 0
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-08-21，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏