摘要:先用处理左右边界上的换成再用处理上下边界除去四角的换成把剩下的没有被处理过,也就是被包围的置为把所有暂时置为的不被包围的换回如当前字符的坐标越界不是,返回是的都置为,然后迭代其上下左右各点
Problem
Given a 2D board containing "X" and "O", capture all regions surrounded by "X".
A region is captured by flipping all "O""s into "X""s in that surrounded region.
X X X X X O O X X X O X X O X X
After capture all regions surrounded by "X", the board should be:
X X X X X X X X X X X X X O X XSolution
public class Solution { public void surroundedRegions(char[][] board) { // Write your code here if (board == null || board.length < 2 || board[0].length < 2) return; int m = board.length; int n = board[0].length; //先用bfs处理左右边界上的"O"(换成"#") for (int i = 0; i < m; i++) { if (board[i][0] == "O") { bfs(board, i, 0); } if (board[i][n-1] == "O") { bfs(board, i, n-1); } } //再用bfs处理上下边界(除去四角)的"O"(换成"#") for (int i = 1; i < n-1; i++) { if (board[0][i] == "O") { bfs(board, 0, i); } if (board[m-1][i] == "O") { bfs(board, m-1, i); } } //把剩下的没有被处理过,也就是被包围的"O"置为"X" for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == "O") { board[i][j] = "X"; } } } //把所有暂时置为"#"的不被包围的"O"换回"O" for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == "#") { board[i][j] = "O"; } } } } public void bfs(char[][] board, int row, int col) { //如当前字符的坐标越界or不是"O",返回 if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != "O") { return; } //是"O"的都置为"#",然后迭代其上下左右各点 board[row][col] = "#"; bfs(board, row-1, col); bfs(board, row+1, col); bfs(board, row, col-1); bfs(board, row, col+1); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65412.html
摘要:将所有和边界相连的都标记出来。那么当我重新遍历数组的时候,剩下的则是被完全包围的。 题目要求 Given a 2D board containing X and O (the letter O), capture all regions surrounded by X. A region is captured by flipping all Os into Xs in that s...
摘要:原题链接边缘搜索替换法复杂度时间空间思路从矩阵的四条边上的点作为起点,搜索连续的一块区域上值为的点并赋为一个临时变量。对四条边上所有点都进行过这个步骤后,矩阵内剩余的就是被包围的。 Surrounded Regions Given a 2D board containing X and O, capture all regionssurrounded by X. A region i...
摘要:不得不说,对于这道题而言,是一种很木讷的模板。主函数按矩阵大小建立一个类进行后续操作一个结点用来连接边角不可能被围绕的一个函数对矩阵元素进行结点线性化。同理,,,在主函数中初始化后调用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...
摘要:并查集包括查询和联合,主要使用不相交集合查询主要是用来决定不同的成员是否在一个子集合之内联合主要是用来把多个子集合成一个集合的实际运用计算机网络检查集群是否联通电路板检查不同的电路元件是否联通初始化联通与检测与是否联通返回联通的数 并查集(Union-Find)包括查询(Find)和联合(Union),主要使用不相交集合(Disjoint-Sets)查询(Find)主要是用来决定不同的...
阅读 3094·2021-09-22 15:05
阅读 2708·2019-08-30 15:56
阅读 995·2019-08-29 17:09
阅读 744·2019-08-29 15:12
阅读 2028·2019-08-26 11:55
阅读 2941·2019-08-26 11:52
阅读 3325·2019-08-26 10:29
阅读 1328·2019-08-23 17:19