LeetCode-130. 被围绕的区域
问题地址
LeetCode130. 被围绕的区域
问题描述
规则
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例
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’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解析
解题思路
根据规则任何边界上的O及与之相关联的O都不会被填充为X，所以我们可以分两步操作：
1. 找出边界O及与其相联通的O，并将其标为P。从边界开始遍历矩阵，当边界上的元素[x][y]==’O’时，我们需要判断与其相邻的元素是否为’O’。使用[x][y]表示矩阵中的任意元素，与[x][y]相邻的元素的坐标为：
2. 遍历矩阵将O填充为X，将P填充为O；
复杂度分析：
- 时间复杂度分析，第一遍需要找出边界为O且与其相邻为O的元素并标为P，第二遍需要遍历整个矩阵将其中的O填充为X，将其中的P填充为O。所以需要遍历2遍。即O(2rowscols)
- 因为在查找及替换过程中均不需要开辟新的空间存储元素。空间复杂度为O(rows*cols)
- 综上本题的时间复杂度、空间复杂度为：
- 时间复杂度为：O(rows*cols)；
- 空间复杂度为：O(rows*cols)；
定位问题：
根据规则我们可以将找出被X包围的区域的问题转为找出与边界为O且与之相联通的元素；
数据操作分析：
在遍历中填充元素；
- 首先处理上下边界，即
x=[0,xlen);y={0,yLen-1}:
- 然后处理左右边界，即
x={0,xLen-1};y=[1, yLen):
编码实现：
public class Surroundedregions {
public static void main(String[] args) {
char[][] chars = {
{'X', 'O', 'X', 'X'},//x=0
{'X', 'X', 'O', 'X'},//x=1
{'X', 'O', 'O', 'X'},//x=2
{'X', 'X', 'X', 'X'}//x=3
};
solve(chars);
}
public static void solve(char[][] board) {
int xLen = board.length;
if (xLen == 0) return;
int yLen = board[0].length;
for (int i = 0; i < yLen; i++) {
mask(board, 0, i, xLen, yLen);
mask(board, xLen - 1, i, xLen, yLen);
}
for (int i = 1; i < xLen - 1; i++) {
mask(board, i, 0, xLen, yLen);
mask(board, i, yLen - 1, xLen, yLen);
}
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
if (board[i][j] == 'P') {
board[i][j] = 'o';//用小写表示被替换过
} else if (board[i][j] == 'O') {
board[i][j] = 'x';
}
}
}
}
private static void mask(char[][] board, int x, int y, int xLen, int yLen) {
if (x < 0 || x >= xLen || y < 0 || y >= yLen || board[x][y] != 'O') return;
board[x][y] = 'P';
mask(board, x - 1, y, xLen, yLen);
mask(board, x, y + 1, xLen, yLen);
mask(board, x + 1, y, xLen, yLen);
mask(board, x, y - 1, xLen, yLen);
}
}
官方解法
- 广度优先搜索
– 思路：我们可以使用广度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A。
– 复杂度分析：
– 时间复杂度：O(n \times m)O(n×m)，其中 nn 和 mm 分别为矩阵的行数和列数。广度优先搜索过程中，每一个点至多只会被标记一次。
– 空间复杂度：O(n \times m)O(n×m)，其中 nn 和 mm 分别为矩阵的行数和列数。主要为广度优先搜索的队列的开销。
class Solution {
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
public void solve(char[][] board) {
int n = board.length;
if (n == 0) {
return;
}
int m = board[0].length;
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') {
queue.offer(new int[]{i, 0});
}
if (board[i][m - 1] == 'O') {
queue.offer(new int[]{i, m - 1});
}
}
for (int i = 1; i < m - 1; i++) {
if (board[0][i] == 'O') {
queue.offer(new int[]{0, i});
}
if (board[n - 1][i] == 'O') {
queue.offer(new int[]{n - 1, i});
}
}
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
board[x][y] = 'A';
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
continue;
}
queue.offer(new int[]{mx, my});
}
}
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';
}
}
}
}
}
- 深度优先搜索
– 思路：我们可以使用深度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A。
– 复杂度分析：
– 时间复杂度：O(n \times m)O(n×m)，其中 nn 和 mm 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
– 空间复杂度：O(n \times m)O(n×m)，其中 nn 和 mm 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。
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);
}
}