题目地址(130. 被围绕的区域)
https://leetcode-cn.com/problems/surrounded-regions/
题目描述
复制 给定一个二维的矩阵,包含 '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'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
前置知识
公司
思路
我们需要将所有被 X 包围的 O 变成 X,并且题目明确说了边缘的所有 O 都是不可以变成 X 的。
其实我们观察会发现,我们除了边缘的 O 以及和边缘 O 连通的 O 是不需要变成 X 的,其他都要变成 X。
经过上面的思考,问题转化为连通区域问题。 这里我们需要标记一下边缘的O以及和边缘O连通的O
。 我们当然可以用额外的空间去存,但是对于这道题目而言,我们完全可以 mutate。这样就空间复杂度会好一点。
整个过程如图所示:
我将边缘的O以及和边缘O连通的O
标记为了 "A"
关键点解析
代码
复制 /*
* @lc app=leetcode id=130 lang=javascript
*
* [130] Surrounded Regions
*/
// 将O以及周边的O转化为A
function mark (board , i , j , rows , cols) {
if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O" )
return ;
board[i][j] = "A" ;
mark (board , i + 1 , j , rows , cols);
mark (board , i - 1 , j , rows , cols);
mark (board , i , j + 1 , rows , cols);
mark (board , i , j - 1 , rows , cols);
}
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const rows = board . length ;
if (rows === 0 ) return [];
const cols = board[ 0 ]. length ;
for ( let i = 0 ; i < rows; i ++ ) {
for ( let j = 0 ; j < cols; j ++ ) {
if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1 ) {
mark (board , i , j , rows , cols);
}
}
}
for ( let i = 0 ; i < rows; i ++ ) {
for ( let j = 0 ; j < cols; j ++ ) {
if (board[i][j] === "O" ) {
board[i][j] = "X" ;
} else if (board[i][j] === "A" ) {
board[i][j] = "O" ;
}
}
}
return board;
};
Python Code:
复制 class Solution :
def solve ( self , board : List [ List [ str ]] ) -> None :
"""
Do not return anything, modify board in-place instead.
"""
# 如果数组长或宽小于等于2,则不需要替换
if len (board) <= 2 or len (board[ 0 ]) <= 2 :
return
row , col = len (board), len (board[ 0 ])
def dfs ( i , j ):
"""
深度优先算法,如果符合条件,替换为A并进一步测试,否则停止
"""
if i < 0 or j < 0 or i >= row or j >= col or board [ i ] [j] != 'O' :
return
board [ i ] [j] = 'A'
dfs (i - 1 , j)
dfs (i + 1 , j)
dfs (i, j - 1 )
dfs (i, j + 1 )
# 从外围开始
for i in range (row):
dfs (i, 0 )
dfs (i, col - 1 )
for j in range (col):
dfs ( 0 , j)
dfs (row - 1 , j)
# 最后完成替换
for i in range (row):
for j in range (col):
if board [ i ] [j] == 'O' :
board [ i ] [j] = 'X'
elif board [ i ] [j] == 'A' :
board [ i ] [j] = 'O'
CPP Code:
复制 class Solution {
int M , N , dirs [ 4 ][ 2 ] = {{ 0 , 1 } , { 0 , - 1 } , { 1 , 0 } , { - 1 , 0 }};
void dfs ( vector < vector < char >> & board , int x , int y) {
if (x < 0 || x >= M || y < 0 || y >= N || board [x][y] != 'O' ) return ;
board [x][y] = '#' ;
for ( auto & dir : dirs) dfs (board , x + dir [ 0 ] , y + dir [ 1 ]);
}
public :
void solve ( vector < vector < char >> & board) {
if ( board . empty () || board [ 0 ] . empty ()) return ;
M = board . size () , N = board [ 0 ] . size ();
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 ( auto & row : board) {
for ( auto & cell : row) {
cell = cell == '#' ? 'O' : 'X' ;
}
}
}
};
相关题目
解题模板是一样的
复杂度分析
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。