一、题目
1、算法题目
“给定一个矩阵，矩阵由字符X和O组成，找出所有被X包围的区域，将区域内的所有O替换成X。”
题目链接：
来源：力扣（LeetCode）
链接： 130. 被围绕的区域 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 '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"]] 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。 复制代码
示例 2： 输入： board = [["X"]] 输出： [["X"]] 复制代码
二、解题
1、思路分析
本题要求将所有被字母X包围的字母O都变成X，所以要找出那些O是被包围的。
题意中有说，任何边界的O都不会被X包围，也就是说，对于每一个边界上的O，以它为起点，标记所有与它直接或间接相连的O，遍历这个矩阵，对于每一个字母：
- 如果该字母被标记过，则该字母不被包围，将其改成字母O
- 如果该字母没有被标记，则该字母被包围，将其改成字母X
OK，思路有了，接下来就是使用深度优先算法去遍历搜索实现标记操作。
2、代码实现
代码参考：
class Solution { int n, m; public void solve(char[][] board) { n = board.length; if (n == 0) { return; } m = board[0].length; for (int i = 0; i < n; i++) { dfs(board, i, 0); dfs(board, i, m - 1); } for (int i = 1; i < m - 1; i++) { dfs(board, 0, i); dfs(board, n - 1, i); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 'A') { board[i][j] = 'O'; } else if (board[i][j] == 'O') { board[i][j] = 'X'; } } } } public void dfs(char[][] board, int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || 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); } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度：O(n * m)
其中n和m分别是矩阵的行数和列数。
空间复杂度：O(n * m)
其中n和m分别是矩阵的行数和列数。
三、总结
本题是将找到被X包围的O的问题，转化为找到所有在边界上的O，以及跟边界上的O相连的O的问题。
然后标记所有在边界的O以及跟边界的O相连的O，然后使用深度优先搜索算法，根据不同的情况进行替换即可。
