130. 被围绕的区域
区域 130 围绕
2023-09-14 09:01:28 时间
130. 被围绕的区域
给你一个 m ∗ n m * n m∗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”]]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’
思路(DFS)
- 首先对边界上每一个’O’做深度优先搜索,将与其相连的所有’O’改为’-'。
- 然后遍历矩阵,将矩阵中所有’O’改为’X’,
- 最后将矩阵中所有’-‘变为’O’。
代码:(Java)
public class dfs_surronded {
public static void main(String[] args) {
// TODO 自动生成的方法存根
char [][] board = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X'},
{'X', 'X', 'O', 'O'},
{'O', 'X', 'X', 'X'}
};
solve(board);
}
private static int m, n;
private static int [][] dircetion = {{1,0},{0,1},{-1,0},{0,-1}};
public static void solve(char[][] board) {
if(board == null || board.length == 0) {
return;
}
m = board.length;
n = board[0].length;
for(int i = 0; i < m; i++) {
if(board[i][0] == 'O') {
dfs(i, 0, board);
}
if(board[i][n-1] == 'O') {
dfs(i, n-1, board);
}
}
for(int j = 1; j < n - 1; j++) {
if(board[0][j] == 'O') {
dfs(0, j, board);
}
if(board[m-1][j] == 'O') {
dfs(m-1, j, board);
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] == '-') {
board[i][j] = 'O';
}
System.out.print(board[i][j] + " ");
}
System.out.println();
}
return;
}
private static void dfs(int r, int c, char[][] board) {
// TODO 自动生成的方法存根
if(r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O')
return;
board[r][c] = '-';
for(int dir[] : dircetion) {
dfs(r+dir[0], c+dir[1], board);
}
return;
}
}
运行结果:
复杂度分析:
- 时间复杂度:O(n×m),其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中,每一个点至多只会被标记一次。
- 空间复杂度:O(n×m),其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。
注:仅供学习参考
来源:力扣
相关文章
- ios uiview touchesBegan 判断点击区域是否在某个view上
- 【金猿技术展】 一种面板缺陷区域检测方法、装置、电子设备及存储介质——面向面板缺陷智能检测与分类关键技术
- 作业区域人数超员预警系统
- OSPF 网络类型+特殊区域
- 【Android 内存优化】Bitmap 长图加载 ( BitmapRegionDecoder 简介 | BitmapRegionDecoder 使用流程 | 区域解码加载示例 )
- 【Linux 内核 内存管理】分区伙伴分配器 ① ( 分区伙伴分配器源码数据结构 | free_area 空闲区域数组 | MAX_ORDER 宏定义 | 空闲区域的页最大阶数 )
- JVM的内存区域划分详解编程语言
- php socket 读取缓存区域详解编程语言
- 查看Redis服务区域开启状态分析(查看redis开启状态)
- js中点击空白区域时文本框与隐藏层的显示与影藏问题