目录
- 题目链接
- 注意点
- 解法
- 小结
题目链接
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效率都差不多
