文章目录题目解析方向向量BFS广度优先搜索算法原理全局变量层序遍历细节问题代码实现DFS深度优先搜索算法原理全局变量dfs 函数函数头函数体细节问题代码实现题目链接529. 扫雷游戏题目解析首先介绍一下什么是FloodFill算法FloodFill算法也称为洪水填充算法指的是在区域中找到性质相同的联通块注意这里的联通块指的是上下左右相邻斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。题目给出一个大小为m x n的二维字符矩阵board表示扫雷游戏的盘面其中M代表一个未被挖出的地雷E代表一个未被挖出的空方块B代表周围没有地雷的已被挖出的空方块周围指的是上下左右以及主、副对角线方向上的方格数字1~8表示与该已被挖出的方块相邻的地雷数量X表示一个已被挖出的地雷再给出一个数组click其中的click[r, c]表示在未被挖出的方块中的下一个点击位置。根据以下规则我们需要返回相应位置被点击之后的盘面如果一个地雷M被挖出游戏直接结束将它修改为X。如果一个周围没有地雷的空方块E被挖出将它的值修改为B并且将所有与其相邻的未被挖出的方块都挖出来。如果一个周围有至少一个地雷的空方块E被挖出将其值修改为数字1到8表示周围地雷的个数。如果在此次点击中没有更多的空方块可以被挖出返回盘面。下面给出两个例子便于理解例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]抽象成二维字符矩阵如下EEEEEEEMEEEEEEEEEEEE我们接下来点击的位置是click [3, 0]即矩阵中的左下角位置的空方格E。点击之后的盘面如下B1E1BB1M1BB111BBBBBB我们需要返回的结果[[“B”,“1”,“E”,“1”,“B”],[“B”,“1”,“M”,“1”,“B”],[“B”,“1”,“1”,“1”,“B”],[“B”,“B”,“B”,“B”,“B”]]例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]抽象成二维字符矩阵B1E1BB1M1BB111BBBBBB点击的位置是click [1, 2]即地雷M这时候将该位置的值改为X后直接结束游戏。点击后的盘面B1E1BB1X1BB111BBBBBB返回的结果[[“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};层序遍历我们使用一个队列实现层序遍历的操作队列存储与〖row, col〗位置相连的单元格坐标当队列不为空时一直取出队首元素获取坐标然后根据队首元素的坐标统计该位置周围地雷的数量当地雷个数为0时就根据队首元素的坐标搜索上下左右以及四个对角线找到符合条件未被挖掘的空方格E的单元格之后将其值改为B然后入队当地雷个数不为0不继续逐层扩展了只将当前队首元素位置的值改为地雷个数然后重新查看队列当队列为空层序遍历完毕由于我们每次扫描矩阵边界时都要进行一次层序遍历操作因此将该操作封装为一个方法。细节问题当点击位置board[click[0]][click[1]]的值是地雷M我们就只修改点击位置的值为X然后直接返回矩阵board即可。我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法以提升代码的可读性。代码实现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){// 初始化boardgivenBoard;mboard.length;nboard[0].length;introwclick[0],colclick[1];// 判断点击位置是否为地雷if(board[row][col]M){board[row][col]X;returnboard;}// 从点击位置开始宽搜bfs(row,col);returnboard;}publicvoidbfs(introw,intcol){// 使用队列存储与[row,col]位置相连的单元格坐标Queueint[]queuenewArrayDeque();queue.offer(newint[]{row,col});// 将[row,col]位置的值改为Bboard[row][col]B;// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();// 取出队首元素rowtop[0];coltop[1];// 获取队首元素的坐标intcountMcountMine(row,col);// 统计当前队首元素周围的地雷数量if(countM0){// 若地雷个数为0从当前队首元素位置逐层展开for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]E){board[x][y]B;// 将值改为Bqueue.offer(newint[]{x,y});// 入队}}}}else{// 若地雷个数不为0将当前位置的值改为地雷个数board[row][col](char)(countM0);}}}publicintcountMine(introw,intcol){// 统计地雷个数intret0;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){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然后继续递归若当前位置周围有至少一个地雷那么就将其值修改为地雷的个数然后结束递归细节问题当点击位置board[click[0]][click[1]]的值是地雷M我们就只修改点击位置的值为X然后直接返回矩阵board即可。我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法以提升代码的可读性。代码实现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){// 初始化boardgivenBoard;mboard.length;nboard[0].length;introwclick[0],colclick[1];// 判断点击位置是否为地雷if(board[row][col]M){board[row][col]X;returnboard;}// 从点击位置开始深搜dfs(row,col);returnboard;}publicvoiddfs(introw,intcol){// 先统计该位置周围的地雷个数intcountMcountMine(row,col);if(countM0){// 若地雷个数为0将当前位置的值改为B然后继续递归board[row][col]B;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]E){dfs(x,y);}}}}else{// 若地雷个数不为0将当前位置的值改为地雷个数并结束递归board[row][col](char)(countM0);return;}}publicintcountMine(introw,intcol){// 统计地雷个数intret0;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]M){ret;}}}returnret;}}文章到这里就告一段落了若有错误请尽管指出完 
长河君 · 2026/9/5 7:21:07 · 阅读 1.2k 【BFS/DFS 解决 FloodFill 算法】扫雷游戏
文章目录题目解析方向向量BFS广度优先搜索算法原理全局变量层序遍历细节问题代码实现DFS深度优先搜索算法原理全局变量dfs 函数函数头函数体细节问题代码实现题目链接529. 扫雷游戏题目解析首先介绍一下什么是FloodFill算法FloodFill算法也称为洪水填充算法指的是在区域中找到性质相同的联通块注意这里的联通块指的是上下左右相邻斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。题目给出一个大小为m x n的二维字符矩阵board表示扫雷游戏的盘面其中M代表一个未被挖出的地雷E代表一个未被挖出的空方块B代表周围没有地雷的已被挖出的空方块周围指的是上下左右以及主、副对角线方向上的方格数字1~8表示与该已被挖出的方块相邻的地雷数量X表示一个已被挖出的地雷再给出一个数组click其中的click[r, c]表示在未被挖出的方块中的下一个点击位置。根据以下规则我们需要返回相应位置被点击之后的盘面如果一个地雷M被挖出游戏直接结束将它修改为X。如果一个周围没有地雷的空方块E被挖出将它的值修改为B并且将所有与其相邻的未被挖出的方块都挖出来。如果一个周围有至少一个地雷的空方块E被挖出将其值修改为数字1到8表示周围地雷的个数。如果在此次点击中没有更多的空方块可以被挖出返回盘面。下面给出两个例子便于理解例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]抽象成二维字符矩阵如下EEEEEEEMEEEEEEEEEEEE我们接下来点击的位置是click [3, 0]即矩阵中的左下角位置的空方格E。点击之后的盘面如下B1E1BB1M1BB111BBBBBB我们需要返回的结果[[“B”,“1”,“E”,“1”,“B”],[“B”,“1”,“M”,“1”,“B”],[“B”,“1”,“1”,“1”,“B”],[“B”,“B”,“B”,“B”,“B”]]例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]抽象成二维字符矩阵B1E1BB1M1BB111BBBBBB点击的位置是click [1, 2]即地雷M这时候将该位置的值改为X后直接结束游戏。点击后的盘面B1E1BB1X1BB111BBBBBB返回的结果[[“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};层序遍历我们使用一个队列实现层序遍历的操作队列存储与〖row, col〗位置相连的单元格坐标当队列不为空时一直取出队首元素获取坐标然后根据队首元素的坐标统计该位置周围地雷的数量当地雷个数为0时就根据队首元素的坐标搜索上下左右以及四个对角线找到符合条件未被挖掘的空方格E的单元格之后将其值改为B然后入队当地雷个数不为0不继续逐层扩展了只将当前队首元素位置的值改为地雷个数然后重新查看队列当队列为空层序遍历完毕由于我们每次扫描矩阵边界时都要进行一次层序遍历操作因此将该操作封装为一个方法。细节问题当点击位置board[click[0]][click[1]]的值是地雷M我们就只修改点击位置的值为X然后直接返回矩阵board即可。我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法以提升代码的可读性。代码实现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){// 初始化boardgivenBoard;mboard.length;nboard[0].length;introwclick[0],colclick[1];// 判断点击位置是否为地雷if(board[row][col]M){board[row][col]X;returnboard;}// 从点击位置开始宽搜bfs(row,col);returnboard;}publicvoidbfs(introw,intcol){// 使用队列存储与[row,col]位置相连的单元格坐标Queueint[]queuenewArrayDeque();queue.offer(newint[]{row,col});// 将[row,col]位置的值改为Bboard[row][col]B;// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();// 取出队首元素rowtop[0];coltop[1];// 获取队首元素的坐标intcountMcountMine(row,col);// 统计当前队首元素周围的地雷数量if(countM0){// 若地雷个数为0从当前队首元素位置逐层展开for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]E){board[x][y]B;// 将值改为Bqueue.offer(newint[]{x,y});// 入队}}}}else{// 若地雷个数不为0将当前位置的值改为地雷个数board[row][col](char)(countM0);}}}publicintcountMine(introw,intcol){// 统计地雷个数intret0;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){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然后继续递归若当前位置周围有至少一个地雷那么就将其值修改为地雷的个数然后结束递归细节问题当点击位置board[click[0]][click[1]]的值是地雷M我们就只修改点击位置的值为X然后直接返回矩阵board即可。我们可以将 “统计某位置周围的地雷数量” 这一步单独提出来封装成一个方法以提升代码的可读性。代码实现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){// 初始化boardgivenBoard;mboard.length;nboard[0].length;introwclick[0],colclick[1];// 判断点击位置是否为地雷if(board[row][col]M){board[row][col]X;returnboard;}// 从点击位置开始深搜dfs(row,col);returnboard;}publicvoiddfs(introw,intcol){// 先统计该位置周围的地雷个数intcountMcountMine(row,col);if(countM0){// 若地雷个数为0将当前位置的值改为B然后继续递归board[row][col]B;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]E){dfs(x,y);}}}}else{// 若地雷个数不为0将当前位置的值改为地雷个数并结束递归board[row][col](char)(countM0);return;}}publicintcountMine(introw,intcol){// 统计地雷个数intret0;for(intk0;k8;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(board[x][y]M){ret;}}}returnret;}}文章到这里就告一段落了若有错误请尽管指出完