Every day a Leetcode
题目来源：130. 被围绕的区域
本题给定的矩阵中有三种元素：
- 字母 X；
- 被字母 X 包围的字母 O；
- 没有被字母 X 包围的字母 O。
本题要求将所有被字母 X 包围的字母 O都变为字母 X ，但很难判断哪些 O 是被包围的，哪些 O 不是被包围的。
注意到题目解释中提到：任何边界上的 O 都不会被填充为 X。 我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。
我们可以利用这个性质判断 O 是否在边界上，具体地说：
对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
最后我们遍历这个矩阵，对于每一个字母：
- 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
- 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。
解法1：深度优先搜索
我们可以使用深度优先搜索实现标记操作。
在下面的代码中，我们把标记过的字母 O 修改为字母 A。
代码：
/** @lc app=leetcode.cn id=130 lang=cpp** [130] 被围绕的区域*/// @lc code=start
class Solution
{
public:// 主函数void solve(vector<vector<char>> &board){if (board.empty())return;int m = board.size(), n = m ? board[0].size() : 0;for (int i = 0; i < m; i++){dfs(board, i, 0);dfs(board, i, n - 1);}for (int j = 0; j < n; j++){dfs(board, 0, j);dfs(board, m - 1, j);}for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if (board[i][j] == 'A')board[i][j] = 'O';else if (board[i][j] == 'O')board[i][j] = 'X';}}// 辅函数void dfs(vector<vector<char>> &board, int x, int y){int m = board.size(), n = m ? board[0].size() : 0;if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')return;board[x][y] = 'A';dfs(board, x + 1, y);dfs(board, x - 1, y);dfs(board, x, y + 1);dfs(board, x, y - 1);}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。
解法2：广度优先搜索
我们可以使用广度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A。
代码：
/** @lc app=leetcode.cn id=130 lang=cpp** [130] 被围绕的区域*/// @lc code=start// DFS
// class Solution
// {
// public:
// // 主函数
// void solve(vector<vector<char>> &board)
// {
// if (board.empty())
// return;
// int m = board.size(), n = m ? board[0].size() : 0;
// for (int i = 0; i < m; i++)
// {
// dfs(board, i, 0);
// dfs(board, i, n - 1);
// }
// for (int j = 0; j < n; j++)
// {
// dfs(board, 0, j);
// dfs(board, m - 1, j);
// }
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// {
// if (board[i][j] == 'A')
// board[i][j] = 'O';
// else if (board[i][j] == 'O')
// board[i][j] = 'X';
// }
// }
// // 辅函数
// void dfs(vector<vector<char>> &board, int x, int y)
// {
// int m = board.size(), n = m ? board[0].size() : 0;
// if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
// return;
// board[x][y] = 'A';
// dfs(board, x + 1, y);
// dfs(board, x - 1, y);
// dfs(board, x, y + 1);
// dfs(board, x, y - 1);
// }
// };// BFS
class Solution
{
private:vector<int> direction{-1, 0, 1, 0, -1};public:// 主函数void solve(vector<vector<char>> &board){if (board.empty())return;int m = board.size(), n = m ? board[0].size() : 0;queue<pair<int, int>> q;// 从最外围开始，初始化队列for (int i = 0; i < m; i++){if (board[i][0] == 'O'){q.push(pair<int, int>{i, 0});board[i][0] = 'A';}if (board[i][n - 1] == 'O'){q.push(pair<int, int>{i, n - 1});board[i][n - 1] = 'A';}}for (int j = 0; j < n; j++){if (board[0][j] == 'O'){q.push(pair<int, int>{0, j});board[0][j] = 'A';}if (board[m - 1][j] == 'O'){q.push(pair<int, int>{m - 1, j});board[m - 1][j] = 'A';}}// BFS遍历while (!q.empty()){auto [r, c] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = r + direction[k], y = c + direction[k + 1];if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')continue;q.push(pair<int, int>{x, y});board[x][y] = 'A';}}// 最终修改for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if (board[i][j] == 'A')board[i][j] = 'O';else if (board[i][j] == 'O')board[i][j] = 'X';}}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。广度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为广度优先搜索的队列的开销。
