题解 | #被围绕的区域#
被围绕的区域
https://www.nowcoder.com/practice/3946670643fe4ec2aedcc2be45aed1a9?tpId=117&tqId=39451&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=5166&title=
想做并查集的，结果dfs更容易
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
if (board.empty()) {
return board;
}
// 左右边界
for (int i = 0; i < board.size(); ++i) {
dfs(board, i, 0);
dfs(board, i, board[0].size() - 1);
}
// 上下边界
for (int i = 0; i < board[0].size(); ++i) {
dfs(board, 0, i);
dfs(board, board.size() - 1, i);
}
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == 'A') {
board[i][j] = 'O';
}
}
}
return board;
}
private:
void dfs(std::vector<std::vector<char>> &board, int x, int y) {
if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
return ;
}
if (board[x][y] == 'O') {
board[x][y] = 'A';
dfs(board, x - 1, y);
dfs(board, x + 1, y);
dfs(board, x, y - 1);
dfs(board, x, y + 1);
}
}
};
