一. 这一题也是回溯算法，因为对题目理解不太清楚，所以就直接看大神解法了.
二. 参考
作者：Ac_pipe 链接：https://leetcode-cn.com/problems/surrounded-regions/solution/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/
思路：1. 这道题我们拿到基本就可以确定是图的 dfs、bfs 遍历的题目了。题目中解释说被包围的区间不会存在于边界上，所以我们会想到边界上的 O 要特殊处理，只要把边界上的 O 特殊处理了，那么剩下的 O 替换成 X 就可以了。问题转化为，如何寻找和边界联通的 O.
2. 这时候的 O 是不做替换的。因为和边界是连通的。为了记录这种状态，我们把这种情况下的 O 换成 # 作为占位符，待搜索结束之后，遇到 O 替换为 X（和边界不连通的 O）；遇到 #，替换回 O(和边界连通的 O)。
3. 如何寻找和边界联通的O? 从边界出发，对图进行 dfs 和 bfs 即可。这里简单总结下 dfs 和 bfs。
bfs 递归。可以想想二叉树中如何递归的进行层序遍历。 bfs 非递归。一般用队列存储。 dfs 递归。最常用，如二叉树的先序遍历。 dfs 非递归。一般用 stack。
三. dfs递归
//这个没有使用visited数组标记有无使用过这个数.而是改用不同的符号#去标记. class Solution { public: void dfs(vector<vector<char>>& board, int i, int j) { //终止条件,要不超出范围,要不碰到#或者X. if (i >= board.size() || i < 0 || j < 0 || j >= board[0].size() || board[i][j] == '#' || board[i][j] == 'X') return; //边界的标记为特殊的符号. board[i][j] = '#'; dfs(board, i + 1, j);//下 dfs(board, i - 1, j);//上 dfs(board, i, j + 1);//右 dfs(board, i, j - 1);//左 } void solve(vector<vector<char>>& board) { //边界条件. if (board.size() == 0 || board[0].size() == 0) return; int m = board.size(), n = board[0].size(); bool b; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { //遍历数组,先解决边界的O问题. //如果i,j处于边界上,且为O. //则dfs,深度优先搜索. b = (i == 0 || i == m - 1 || j == 0 || j == n - 1); if (b && board[i][j] == 'O') dfs(board, i, j); } } 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'; } } } };四. 继续参考下一个大神的,可以用作回溯的通用模板了.
作者：windliang 链接：https://leetcode-cn.com/problems/surrounded-regions/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-6/
1. 解法一是从当前节点做 DFS ，然后看它是否能到达边界的 O。那么我们能不能把思路逆转过来呢？
2. 从边界的 O 做 DFS，然后把遇到的 O 都标记一下，这些 O 就是可以连通到边界的。然后把边界的所有的 O 都做一次 DFS ，把 DFS 过程的中的 O 做一下标记。最后我们只需要遍历节点，把没有标记过的 O 改成 X 就可以了。
3. 标记的话，我们可以用一个 visited 二维数组，把访问过的置为 true .(这是一个技巧)
class Solution { public: //记住,传入数组时一定要传入他的地址,不然值不会改变. void dfs(int i, int j, vector<vector<char>>& board, vector<vector<int>>& visited) { if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return; if (visited[i][j] == 1) return; //如果遇到'X',都不满足条件,则直接返回. if (board[i][j] == 'O') { //将当前坐标设置为1,注意是当前的. visited[i][j] = 1; dfs(i + 1, j, board, visited); dfs(i - 1, j, board, visited); dfs(i, j + 1, board, visited); dfs(i, j - 1, board, visited); } } void solve(vector<vector<char>>& board) { //边界条件. if (board.size() == 0 || board[0].size() == 0) return; int m = board.size(), n = board[0].size(); vector<vector<int>> visited(m, vector<int>(n, 0)); //直接把边界找出来对边界处理. for (int j = 0; j < n; j++) { if (board[0][j] == 'O') dfs(0, j, board, visited); if (board[m - 1][j] == 'O') { dfs(m - 1, j, board, visited); } } for (int i = 0; i < m; i++) { if (board[i][0] == 'O') dfs(i, 0, board, visited); if (board[i][n - 1] == 'O') dfs(i, n - 1, board, visited); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (visited[i][j] == 1) board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } };
