LeetCode 130 Surrounded Regions
概述
https://leetcode.com/problems/surrounded-regions/
直接法
每个元素如果四周都是 X 或者是 W，就将其设置为 X。W 意味着该元素的是否可以翻转正待确认。
以下是一个通过了 37/58 测试样例的错误解法：
class Solution {
public:
void solve(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i ++) {
for (int j = 0; j < board[0].size(); j ++) {
helper(board, i, j);
}
}
}
bool helper(vector<vector<char>>& board, int i, int j) {
if (i == -1 || j == -1 || i == board.size() || j == board[0].size()) return false;
if (board[i][j] == 'X') return true;
if (board[i][j] == 'W') return true;
board[i][j] = 'W';
if (helper(board, i + 1, j) && helper(board, i - 1, j) && helper(board, i , j + 1) && helper(board, i, j - 1)) {
board[i][j] = 'X';
return true;
}
board[i][j] = 'O';
return false;
}
};
输入：
[["O","X","X","O","X"],
["X","O","O","X","O"],
["X","O","X","O","X"],
["O","X","O","O","O"],
["X","X","O","X","O"]]
输出（A 是被错误翻转的地方）：
[["O","X","X","O","X"],
["X","X","X","X","O"],
["X","X","X","A","X"],
["O","X","O","O","O"],
["X","X","O","X","O"]]
我还是没想通为啥这个地方会搞错，可以看到其下面的区域是没有搞错的，唯一的解释是， 其下面的区域之前也被搞错了，但是后来被纠正了过来，但是想要被纠正，其就不能是 X 和 W， 所以当时只能是 O，这就意味着其没被搞错，矛盾了啊！所以其下面的全程没被搞错， 但是这样的话其又是怎么导致该各被设置为 X 嘞？代码中只有一个地方可以设置其为 X， 只能上下左右全为 true 啊。
深度优先搜索
遍历四周的点，标记所有与四周相连的 O 为 #，这之后剩下的 O 就是要翻转的 O。 时间复杂度 O(mn)，因为每个元素只被处理一次。
class Solution {
public:
void solve(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i ++) {
for (int j = 0; j < board[0].size(); j ++) {
if (i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1) dfs(board, i, j);
}
}
for (int i = 0; i < board.size(); i ++) {
for (int j = 0; j < board[0].size(); j ++) {
if (board[i][j] == '#') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
void dfs(vector<vector<char>>& board, int i, int j) {
if (i == -1 || j == -1 || i == board.size() || j == board[0].size()) return;
if (board[i][j] == 'O') {
board[i][j] = '#';
dfs(board, i + 1, j);
dfs(board, i - 1, j);
dfs(board, i, j + 1);
dfs(board, i, j - 1);
}
}
};
并查集解法
我看了下，有点麻烦，大致思想是设置一个 dummy 节点，然后遍历四周的 O，设置其与 dummy 连通， 然后遍历棋盘中剩余部分，对其中的 O，设置其与四周的 O 连通。
最后再遍历一遍棋盘，翻转那些不与 dummy 连通的节点就好了。