LeetCode 130题：如何判断并反转被周围区域包围的岛屿？
- 内容介绍
- 文章标签
- 相关推荐
本文共计805个文字，预计阅读时间需要4分钟。
使用DFS解决连通分量问题，关键在于细节的优化。可以从边界入手，任何不在边界上的O都会变成X。也可以反向思考，先找没有包围的节点。具体实现思路：从边界出发，向外探索，寻找与边界相邻的节点。
找联通分量问题用DFS来做，主要是细节的优化。可以从这个地方入手，任何不在边界上的O都会变成X。也可以反向思维先找没有被包围的。具体的实现思路：从边界出发，去找和边界相连的O，把它标记成一个特殊值，再把网格中其他的O标记成X，最后再把第一步标记成特殊值的O还原 一、题目大意标签: 搜索
leetcode.cn/problems/surrounded-regions
给你一个 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"]]
提示：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] 为 'X' 或 'O'
找联通分量问题用DFS来做，主要是细节的优化。可以从这个地方入手，任何不在边界上的O都会变成X。也可以反向思维先找没有被包围的。具体的实现思路：从边界出发，去找和边界相连的O，把它标记成一个特殊值，再把网格中其他的O标记成X，最后再把第一步标记成特殊值的O还原
三、解题方法 3.1 Java实现public class Solution {
public void solve(char[][] board) {
this.m = board.length;
if (this.m == 0) {
return;
}
this.board = board;
this.n = board[0].length;
for (int y = 0; y < m; y++) {
dfs(0, y);
dfs(n - 1, y);
}
for (int x = 0; x < n; x++) {
dfs(x, 0);
dfs(x, m - 1);
}
Map<Character, Character> v = new HashMap<>();
v.put('G', 'O');
v.put('O', 'X');
v.put('X', 'X');
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
switch (board[y][x]) {
case 'G':
board[y][x] = 'O';
break;
case 'O':
board[y][x] = 'X';
break;
case 'X':
board[y][x] = 'X';
}
}
}
}
private char[][] board;
private int m;
private int n;
private void dfs(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') {
return;
}
board[y][x] = 'G';
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
}
四、总结小记
- 2022/6/10 联通分量问题用DFS
本文共计805个文字，预计阅读时间需要4分钟。
使用DFS解决连通分量问题，关键在于细节的优化。可以从边界入手，任何不在边界上的O都会变成X。也可以反向思考，先找没有包围的节点。具体实现思路：从边界出发，向外探索，寻找与边界相邻的节点。
找联通分量问题用DFS来做，主要是细节的优化。可以从这个地方入手，任何不在边界上的O都会变成X。也可以反向思维先找没有被包围的。具体的实现思路：从边界出发，去找和边界相连的O，把它标记成一个特殊值，再把网格中其他的O标记成X，最后再把第一步标记成特殊值的O还原 一、题目大意标签: 搜索
leetcode.cn/problems/surrounded-regions
给你一个 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"]]
提示：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] 为 'X' 或 'O'
找联通分量问题用DFS来做，主要是细节的优化。可以从这个地方入手，任何不在边界上的O都会变成X。也可以反向思维先找没有被包围的。具体的实现思路：从边界出发，去找和边界相连的O，把它标记成一个特殊值，再把网格中其他的O标记成X，最后再把第一步标记成特殊值的O还原
三、解题方法 3.1 Java实现public class Solution {
public void solve(char[][] board) {
this.m = board.length;
if (this.m == 0) {
return;
}
this.board = board;
this.n = board[0].length;
for (int y = 0; y < m; y++) {
dfs(0, y);
dfs(n - 1, y);
}
for (int x = 0; x < n; x++) {
dfs(x, 0);
dfs(x, m - 1);
}
Map<Character, Character> v = new HashMap<>();
v.put('G', 'O');
v.put('O', 'X');
v.put('X', 'X');
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
switch (board[y][x]) {
case 'G':
board[y][x] = 'O';
break;
case 'O':
board[y][x] = 'X';
break;
case 'X':
board[y][x] = 'X';
}
}
}
}
private char[][] board;
private int m;
private int n;
private void dfs(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') {
return;
}
board[y][x] = 'G';
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
}
四、总结小记
- 2022/6/10 联通分量问题用DFS