BFS解决FloodFill算法_被围绕的区域_C++

---

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});}}}}
};

---