BFS解决FloodFill算法_被围绕的区域_C++
- 1. 题目描述
- 2. 算法分析
- 3. 代码实现
1. 题目描述
leetcode链接:https://leetcode.cn/problems/surrounded-regions/description/
给你一个m x n
的矩阵board
,由若干字符'X'
和'O'
组成,捕获 所有 被围绕的区域:
- 连接:一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域:连接所有
'O'
的单元格来形成一个区域。 - 围绕:如果您可以用
'X'
单元格 连接这个区域,并且区域中没有任何单元格位于 board 边缘,则该区域被'X'
单元格围绕。
通过将输入矩阵board
中的所有'O'
替换为'X'
来捕获被围绕的区域。
示例 1:
输入: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]输出: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释:
- 在上图中,底部的区域没有被捕获,因为它在 board 的边缘并且不能被围绕。
2. 算法分析
1. 正面解题:
- 用bfs遍历所有的
O
联通区域,如果遇到边界,则证明这个联通区域不需要修改。如果没有遇到边界,则需要修改。 - 这样做,可以先在遍历时统一修改所有
O
区域,然后将遇到边界的区域还原回来。这就需要我们记录遍历过的位置,十分麻烦。
2. 正难则反:
- 我们可以先统一遍历最外层的一圈,用bfs将与边界相连的
O
联通区域都改为一个别的字符,比如.
。 - 然后再用遍历并修改所有剩下的
O
区域,同时还原.
。
3. 代码实现
class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// 1. 先处理边界上的'O'联通块,全修改成'.'for (int i = 0; i < n; i++){if (board[0][i] == 'O') bfs(board, 0, i);if (board[m - 1][i] == 'O') bfs(board, m - 1, i); }for (int i = 0; i < m; i++){if (board[i][0] == 'O') bfs(board, i, 0);if (board[i][n - 1] == 'O') bfs(board, i, n - 1); }// 2. 还原for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (board[i][j] == '.') board[i][j] = 'O';else if (board[i][j] == 'O') board[i][j] = 'X';}}}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int, int>> q;q.push({i, j});board[i][j] = '.';while(q.size()){auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){board[x][y] = '.';q.push({x, y});}}}}
};