Open grandyang opened 5 years ago
根据大佬的第一种写法做了一个实现,没有遇到 j>1 什么的奇怪问题
class Solution {
public:
void solve(vector<vector<char>>& board) {
int rows = board.size();
if(rows == 0){
return;
}
int cols = board[0].size();
for(int row = 0; row < rows; row++){//遍历四条边
solveCore(board, row, 0);
solveCore(board, row, cols-1);
}
for(int col = 0; col < cols; col++){
solveCore(board, 0, col);
solveCore(board, rows-1, col);
}
for(vector<char>& eles: board){
for(char& ele: eles){
if(ele == 'O'){
ele = 'X';
}
if(ele == '$'){
ele = 'O';
}
}
}
}
private:
void solveCore(vector<vector<char>>& board, int i, int j){
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){
return;
}
board[i][j] = '$';
solveCore(board, i+1, j);
solveCore(board, i-1, j);
solveCore(board, i, j+1);
solveCore(board, i, j-1);
}
};
根据大佬的第一种写法做了一个实现,没有遇到 j>1 什么的奇怪问题
class Solution { public: void solve(vector<vector<char>>& board) { int rows = board.size(); if(rows == 0){ return; } int cols = board[0].size(); for(int row = 0; row < rows; row++){//遍历四条边 solveCore(board, row, 0); solveCore(board, row, cols-1); } for(int col = 0; col < cols; col++){ solveCore(board, 0, col); solveCore(board, rows-1, col); } for(vector<char>& eles: board){ for(char& ele: eles){ if(ele == 'O'){ ele = 'X'; } if(ele == '$'){ ele = 'O'; } } } } private: void solveCore(vector<vector<char>>& board, int i, int j){ if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){ return; } board[i][j] = '$'; solveCore(board, i+1, j); solveCore(board, i-1, j); solveCore(board, i, j+1); solveCore(board, i, j-1); } };
嗯嗯,现在貌似没问题了。
Given a 2D board containing
'X'
and'O'
(the letter O), capture all regions surrounded by'X'
.A region is captured by flipping all
'O'
s into'X'
s in that surrounded region.Example:
After running your function, the board should be:
Explanation:
Surrounded regions shouldn’t be on the border, which means that any
'O'
on the border of the board are not flipped to'X'
. Any'O'
that is not on the border and it is not connected to an'O'
on the border will be flipped to'X'
. Two cells are connected if they are adjacent cells connected horizontally or vertically.这是道关于 XXOO 的题,有点像围棋,将包住的O都变成X,但不同的是边缘的O不算被包围,跟之前那道 Number of Islands 很类似,都可以用 DFS 来解。刚开始我的思路是 DFS 遍历中间的O,如果没有到达边缘,都变成X,如果到达了边缘,将之前变成X的再变回来。但是这样做非常的不方便,在网上看到大家普遍的做法是扫矩阵的四条边,如果有O,则用 DFS 遍历,将所有连着的O都变成另一个字符,比如 \$,这样剩下的O都是被包围的,然后将这些O变成X,把$变回O就行了。代码如下:
解法一:
很久以前,上面的代码中最后一个 if 中必须是 j > 1 而不是 j > 0,为啥 j > 0 无法通过 OJ 的最后一个大数据集合,博主开始也不知道其中奥秘,直到被另一个网友提醒在本地机子上可以通过最后一个大数据集合,于是博主也写了一个程序来验证,请参见验证 LeetCode Surrounded Regions 包围区域的DFS方法,发现 j > 0 是正确的,可以得到相同的结果。神奇的是,现在用 j > 0 也可以通过 OJ 了。
下面这种解法还是 DFS 解法,只是递归函数的写法稍有不同,但是本质上并没有太大的区别,参见代码如下:
解法二:
我们也可以使用迭代的解法,但是整体的思路还是一样的,在找到边界上的O后,然后利用队列 queue 进行 BFS 查找和其相连的所有O,然后都标记上美元号。最后的处理还是先把所有的O变成X,然后再把美元号变回O即可,参见代码如下:
解法三:
Github 同步地址:
https://github.com/grandyang/leetcode/issues/130
类似题目:
Number of Islands
Walls and Gates
参考资料:
https://leetcode.com/problems/surrounded-regions/
https://leetcode.com/problems/surrounded-regions/discuss/41895/Share-my-clean-Java-Code
https://leetcode.com/problems/surrounded-regions/discuss/41825/Simple-BFS-solution-easy-to-understand
https://leetcode.com/problems/surrounded-regions/discuss/41612/A-really-simple-and-readable-C%2B%2B-solutionuff0conly-cost-12ms
LeetCode All in One 题目讲解汇总(持续更新中...)