---

題目鏈接：

130. 被圍繞的區域

---

題目描述：

---

解法

BFS一層層剝開。

---

C++ 算法代碼：

class Solution {// 定義四個方向的偏移量：右、左、下、上int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};// 網格的行數和列數int m, n;public:// 主函數：處理被'X'包圍的區域void solve(vector<vector<char>>& board) {// 獲取網格的行數和列數m = board.size(), n = board[0].size();// 1. 處理四條邊上的'O'及其連通區域// 上邊界for (int j = 0; j < n; j++) {if (board[0][j] == 'O')bfs(board, 0, j);  // 標記為'.'}// 下邊界for (int j = 0; j < n; j++) {if (board[m - 1][j] == 'O')bfs(board, m - 1, j);  // 標記為'.'}// 左邊界for (int i = 0; i < m; i++) {if (board[i][0] == 'O')bfs(board, i, 0);  // 標記為'.'}// 右邊界for (int i = 0; i < m; i++) {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] == 'O') {// 這些'O'是被'X'包圍的，需要改為'X'board[i][j] = 'X';} else if (board[i][j] == '.') {// 這些'.'是之前從邊界'O'擴展來的，恢復為'O'board[i][j] = 'O';}}}}// BFS輔助函數：將與(i,j)相連的所有'O'標記為'.'void bfs(vector<vector<char>>& board, int i, int j) {queue<pair<int, int>> q;q.push({i, j});board[i][j] = '.';  // 標記為'.'，表示這個位置不會被'X'包圍while (!q.empty()) {auto [a, b] = q.front();q.pop();// 遍歷四個方向for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];// 檢查新坐標是否在網格內且為'O'if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {q.push({x, y});board[x][y] = '.';  // 標記為'.'}}}}
};