题目链接
https://leetcode.com/problems/surrounded-regions/
注意点
- 边缘不算包围‘O’
解法
解法一：dfs。找处在边缘上的O然后dfs将与之相邻的O都改为#。处理完之后再把这时候的O改为X,#改为O即可
class Solution {
public:
void solve(vector<vector<char>>& board) {
int n = board.size();
for(int i = 0;i < n;i++)
{
for(int j = 0;j < board[i].size();j++)
{
if((i == 0 || i == n-1 || j == 0 ||j == board[i].size()-1) && board[i][j] == 'O') dfs(board,i,j);
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < board[i].size();j++)
{
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '#') board[i][j] = 'O';
}
}
}
void dfs(vector<vector<char>>& board,int i,int j)
{
if (board[i][j] == 'O')
{
board[i][j] = '#';
if (i > 0 && board[i - 1][j] == 'O')
dfs(board, i - 1, j);
if (j < board[i].size() - 1 && board[i][j + 1] == 'O')
dfs(board, i, j + 1);
if (i < board.size() - 1 && board[i + 1][j] == 'O')
dfs(board, i + 1, j);
if (j > 0 && board[i][j - 1] == 'O')
dfs(board, i, j - 1);
}
}
};
解法二：bfs。基本上一样的思路，还是找处在边缘上的O然后bfs将与之相邻的O都改为#。处理完之后再把这时候的O改为X,#改为O即可
class Solution {
public:
void solve(vector<vector<char>>& board) {
int n = board.size();
for(int i = 0;i < n;i++)
{
for(int j = 0;j < board[i].size();j++)
{
if((i == 0 || i == n-1 || j == 0 ||j == board[i].size()-1) && board[i][j] == 'O') dfs(board,i,j);
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < board[i].size();j++)
{
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '#') board[i][j] = 'O';
}
}
}
void dfs(vector<vector<char>>& board,int i,int j)
{
if (board[i][j] == 'O')
{
board[i][j] = '#';
if (i > 0 && board[i - 1][j] == 'O')
dfs(board, i - 1, j);
if (j < board[i].size() - 1 && board[i][j + 1] == 'O')
dfs(board, i, j + 1);
if (i < board.size() - 1 && board[i + 1][j] == 'O')
dfs(board, i + 1, j);
if (j > 0 && board[i][j - 1] == 'O')
dfs(board, i, j - 1);
}
}
};
小结
- 这道题dfs和bfs效率都差不多