企业官网建设流程全解析

题目链接：529. 扫雷游戏

题目解析

首先介绍一下什么是FloodFill算法：

FloodFill算法，也称为洪水填充算法，指的是在区域中找到性质相同的联通块，注意这里的联通块指的是上下左右相邻，斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。

题目给出一个大小为m x n的二维字符矩阵board，表示扫雷游戏的盘面，其中：

• M代表一个未被挖出的地雷
• E代表一个未被挖出的空方块
• B代表周围没有地雷的已被挖出的空方块（周围指的是上下左右以及主、副对角线方向上的方格）
• 数字（'1'~'8'）表示与该已被挖出的方块相邻的地雷数量
• X表示一个已被挖出的地雷

再给出一个数组click，其中的click[r, c]表示在未被挖出的方块中的下一个点击位置。

根据以下规则，我们需要返回相应位置被点击之后的盘面：

1. 如果一个地雷（M）被挖出，游戏直接结束，将它修改为X。
2. 如果一个周围没有地雷的空方块（E）被挖出，将它的值修改为B，并且将所有与其相邻的未被挖出的方块都挖出来。
3. 如果一个周围有至少一个地雷的空方块（E）被挖出，将其值修改为数字（1到8）表示周围地雷的个数。
4. 如果在此次点击中，没有更多的空方块可以被挖出，返回盘面。

下面给出两个例子便于理解：

1. 例1

• 输入：board = [[“E”,“E”,“E”,“E”,“E”],[“E”,“E”,“M”,“E”,“E”],[“E”,“E”,“E”,“E”,“E”],[“E”,“E”,“E”,“E”,“E”]], click = [3,0]

抽象成二维字符矩阵如下：

我们接下来点击的位置是click = [3, 0]，即矩阵中的左下角位置的空方格（E）。

点击之后的盘面如下：

我们需要返回的结果：

• [[“B”,“1”,“E”,“1”,“B”],[“B”,“1”,“M”,“1”,“B”],[“B”,“1”,“1”,“1”,“B”],[“B”,“B”,“B”,“B”,“B”]]

2. 例2

• 输入：board = [[“B”,“1”,“E”,“1”,“B”],[“B”,“1”,“M”,“1”,“B”],[“B”,“1”,“1”,“1”,“B”],[“B”,“B”,“B”,“B”,“B”]], click = [1,2]

抽象成二维字符矩阵：

点击的位置是click = [1, 2]，即地雷（M），这时候将该位置的值改为X后直接结束游戏。

点击后的盘面：

返回的结果：

• [[“B”,“1”,“E”,“1”,“B”],[“B”,“1”,“X”,“1”,“B”],[“B”,“1”,“1”,“1”,“B”],[“B”,“B”,“B”,“B”,“B”]]

方向向量

在继续之前，有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右以及四个对角线八个方向的操作。

本题除了上下左右这四个方向之外，还需要访问四个对角线方向，坐标〖i, j〗的上下左右及四个对角线八个坐标是在i和j加上了 0、1、-1 ：

• 上下坐标：〖i + (-1), j + 0〗和〖i + 1, j + 0〗；
• 左右坐标：〖i + 0, j + (-1)〗和〖i + 0, j + 1〗；
• 左上角和右上角坐标：〖i + (-1), j + (-1)〗和〖i + (-1), j + 1〗
• 左下角和右下角坐标：〖i + 1, j + (-1)〗和〖i + 1, j + 1〗

因此定义两个方向数组：dx = {0, 0, -1, 1, -1, -1, 1, 1} 和 dy = {-1, 1, 0, 0, -1, 1, 1, -1}。

在需要访问时，通过 〖row, col〗坐标和八次循环依次访问即可。

BFS：广度优先搜索

算法原理

采用广度优先搜索的思路：

• 从题目给出的点击位置click开始宽搜
• 到达一个位置时，先统计周围地雷的个数，然后根据地雷个数来判断：
• • 如果地雷个数为0，就将当前位置的值改为B然后继续逐层展开
• • 如果地雷个数不为0，将当前位置的值改为地雷的个数

全局变量

为了方便访问，将题目所给的二维字符矩阵board改为全局变量；矩阵的大小m和n；两个辅助我们访问到某个位置的周围八个方向的方向数组dx和dy。

char[][]board;intm,n;int[]dx={0,0,-1,1,-1,-1,1,1};int[]dy={-1,1,0,0,-1,1,1,-1};

层序遍历

我们使用一个队列实现层序遍历的操作：

1. 队列存储与〖row, col〗位置相连的单元格坐标
2. 当队列不为空时，一直取出队首元素获取坐标，然后根据队首元素的坐标统计该位置周围地雷的数量
3. 当地雷个数为0时，就根据队首元素的坐标搜索上下左右以及四个对角线，找到符合条件（未被挖掘的空方格E）的单元格之后，将其值改为B，然后入队；当地雷个数不为0，不继续逐层扩展了，只将当前队首元素位置的值改为地雷个数，然后重新查看队列
4. 当队列为空，层序遍历完毕

由于我们每次扫描矩阵边界时都要进行一次层序遍历操作，因此将该操作封装为一个方法。

细节问题

1. 当点击位置board[click[0]][click[1]]的值是地雷（M），我们就只修改点击位置的值为X，然后直接返回矩阵board即可。
2. 我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法，以提升代码的可读性。

代码实现

classSolution{char[][]board;// 题目所给的矩阵intm,n;// 矩阵的大小// 辅助访问上下左右以及四个对角线八个方向的数组int[]dx={0,0,-1,1,-1,-1,1,1};int[]dy={-1,1,0,0,-1,1,1,-1};publicchar[][]updateBoard(char[][]givenBoard,int[]click){// 初始化board=givenBoard;m=board.length;n=board[0].length;introw=click[0],col=click[1];// 判断点击位置是否为地雷if(board[row][col]=='M'){board[row][col]='X';returnboard;}// 从点击位置开始宽搜bfs(row,col);returnboard;}publicvoidbfs(introw,intcol){// 使用队列存储与[row,col]位置相连的单元格坐标Queue<int[]>queue=newArrayDeque<>();queue.offer(newint[]{row,col});// 将[row,col]位置的值改为'B'board[row][col]='B';// 层序遍历while(!queue.isEmpty()){int[]top=queue.poll();// 取出队首元素row=top[0];col=top[1];// 获取队首元素的坐标intcountM=countMine(row,col);// 统计当前队首元素周围的地雷数量if(countM==0){// 若地雷个数为0，从当前队首元素位置逐层展开for(intk=0;k<8;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n){if(board[x][y]=='E'){board[x][y]='B';// 将值改为'B'queue.offer(newint[]{x,y});// 入队}}}}else{// 若地雷个数不为0，将当前位置的值改为地雷个数board[row][col]=(char)(countM+'0');}}}publicintcountMine(introw,intcol){// 统计地雷个数intret=0;for(intk=0;k<8;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n){if(board[x][y]=='M'){ret++;}}}returnret;}}

DFS：深度优先搜索

算法原理

采用深度优先搜索的思路：

• 从题目给出的点击位置click开始递归
• 到达一个位置时，先统计周围地雷的个数，然后根据地雷个数来判断：
• • 如果地雷个数为0，就将当前位置的值改为B然后继续递归
• • 如果地雷个数不为0，此时将当前位置的值改为地雷的个数，然后结束递归

全局变量

为了递归方便，将题目所给的二维字符矩阵board改为全局变量；矩阵的大小m和n；两个辅助我们访问到某个位置的周围八个方向的方向数组dx和dy。

char[][]board;intm,n;int[]dx={0,0,-1,1,-1,-1,1,1};int[]dy={-1,1,0,0,-1,1,1,-1};

dfs 函数

函数头

我们给 dfs 函数的任务是：根据特定位置周围的地雷个数来决定是否继续递归展开，因此我们的参数只需要坐标即可，返回值是 void。

voiddfs(introw,intcol);

函数体

dfs 函数任务的具体是：

• 根据某个位置周围的地雷个数，判断：
• • 若当前位置周围没有地雷，并且它的值是E，就将其值修改为B然后继续递归
• • 若当前位置周围有至少一个地雷，那么就将其值修改为地雷的个数，然后结束递归

细节问题

1. 当点击位置board[click[0]][click[1]]的值是地雷（M），我们就只修改点击位置的值为X，然后直接返回矩阵board即可。
2. 我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法，以提升代码的可读性。

代码实现

classSolution{char[][]board;intm,n;// 辅助访问上下左右以及四个对角线八个方向的数组int[]dx={0,0,-1,1,-1,-1,1,1};int[]dy={-1,1,0,0,-1,1,1,-1};publicchar[][]updateBoard(char[][]givenBoard,int[]click){// 初始化board=givenBoard;m=board.length;n=board[0].length;introw=click[0],col=click[1];// 判断点击位置是否为地雷if(board[row][col]=='M'){board[row][col]='X';returnboard;}// 从点击位置开始深搜dfs(row,col);returnboard;}publicvoiddfs(introw,intcol){// 先统计该位置周围的地雷个数intcountM=countMine(row,col);if(countM==0){// 若地雷个数为0，将当前位置的值改为'B'然后继续递归board[row][col]='B';for(intk=0;k<8;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n){if(board[x][y]=='E'){dfs(x,y);}}}}else{// 若地雷个数不为0，将当前位置的值改为地雷个数并结束递归board[row][col]=(char)(countM+'0');return;}}publicintcountMine(introw,intcol){// 统计地雷个数intret=0;for(intk=0;k<8;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n){if(board[x][y]=='M'){ret++;}}}returnret;}}

文章到这里就告一段落了，若有错误请尽管指出～

完