岛屿问题
问题一：岛屿数量
问题描述
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。dfs求解
定义一与区域相同大小的布尔型二维数组access，access[i] [j]用于标识该位置是否被访问过。依次从每个位置开始对其进行dfs，如此每次可以访问一片相连的岛屿，。如此可以得到共有多少片区域。
实现代码如下：
class Solution {
public int[][] directs = new int[][] {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
public int numIslands(char[][] grid) {
if(grid.length == 0){
return 0;
}
int M = grid.length;
int N = grid[0].length;
boolean[][] access = new boolean[M][N];
int count = 0;
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
if(grid[i][j] == '1' && !access[i][j]){
count++;
dfs(i, j, grid, access);
}
}
}
return count;
}
public void dfs(int i, int j, char[][] grid, boolean[][] access){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' || access[i][j]){
return;
}
access[i][j] = true;
for(int[] direct : directs){
dfs(i + direct[0], j + direct[1], grid, access);
}
}
}并查集求解
一个很容易想到的方法就是利用并查集求解，对相邻的陆地区域使用并操作，最终统计共有多少个不同的集合。实现代码如下：
class Solution {
public static class Unionfind{
private int[][][] parent;
public Unionfind(int M, int N){
// parent[i][j][0] parent所对应的行数 parent[i][j][1]为其所对应的列数
this.parent = new int[M][N][2];
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
// 初始化 各自为一个小岛
parent[i][j][0] = i;
parent[i][j][1] = j;
}
}
}
public void union(int x1, int y1, int x2, int y2){
int[] root1 = find(x1, y1);
int[] root2 = find(x2, y2);
parent[root1[0] ] [root1[1] ][0] = root2[0];
parent[root1[0] ] [root1[1] ][1] = root2[1];
}
public int[] find(int x, int y){
int rootX = x;
int rootY = y;
while(parent[rootX][rootY][0] != rootX || parent[rootX][rootY][1] != rootY){
// 使用tempX tempY为了避免当前的rootX影响到当前的rootY
int tempX = parent[rootX][rootY][0];
int tempY = parent[rootX][rootY][1];
rootX = tempX;
rootY = tempY;
}
while(parent[x][y][0] != x || parent[x][y][1] != y){
int tempX = parent[x][y][0];
int tempY = parent[x][y][1];
parent[x][y][0] = rootX;
parent[x][y][1] = rootY;
x = tempX;
y = tempY;
}
return new int[]{rootX, rootY};
}
}
public int numIslands(char[][] grid) {
if(grid.length == 0){
return 0;
}
int M = grid.length;
int N = grid[0].length;
Unionfind uf = new Unionfind(M, N);
// init
// 把第一列能连的连到一块
for(int i = 1; i < M; i++){
if(grid[i][0] == '1' && grid[i - 1][0] == '1'){
uf.union(i, 0, i - 1, 0);
}
}
// 把第一行能连的连到一块
for(int j = 1; j < N; j++){
if(grid[0][j] == '1' && grid[0][j - 1] == '1'){
uf.union(0, j, 0, j - 1);
}
}
for(int i = 1; i < M; i++){
for(int j = 1; j < N; j++){
if(grid[i][j] == '0'){
continue;
}
if(grid[i - 1][j] == '1'){
uf.union(i, j, i - 1, j);
}
if(grid[i][j - 1] == '1'){
uf.union(i, j, i, j - 1);
}
}
}
Set<String> count = new HashSet<>();
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
if(grid[i][j] == '0'){
continue;
}
int[] root = uf.find(i, j);
count.add(root[0] + " " + root[1]);
}
}
return count.size();
}
}问题二：岛屿的最大面积
问题描述
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
依然使用较为简洁的dfs求解，遍历过程中依然使用access标识当前位置是否被访问过。
定义dfs(i, j) 返回以i j 位置为入口未访问的岛面积，显然
实现代码如下：
class Solution {
// 四个方向
public int[][] directs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1 , 0}};
public int maxAreaOfIsland(int[][] grid) {
if(grid.length == 0){
return 0;
}
int M = grid.length;
int N = grid[0].length;
boolean[][] access = new boolean[M][N];
int ans = 0;
for(int i = 0; i < M; i++){
for(int j = 0; j < N; j++){
ans = Math.max(ans, dfs(i, j, grid, access));
}
}
return ans;
}
public int dfs(int i, int j, int[][] grid, boolean[][] access){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0 || access[i][j]){
return 0;
}
int ans = 1;
access[i][j] = true;
for(int[] direct : directs){
ans += dfs(i + direct[0], j + direct[1], grid, access);
}
return ans;
}
}问题三：被围绕的区域
问题描述
给定一个二维的矩阵，包含 '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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
以边界上的”O”作为入口进行dfs，标识出所有和边界相连通的位置，标识为“U”。如此矩阵中此时剩余的那些“O”就是被“X”所围绕的区域。
因此再遍历该二维矩阵，遇到的“O”全部置为“X”，遇到”U”全部置为“O”。
实现代码如下：
class Solution {
int[][] directs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 将边界区域的‘O’ 先换成‘U’
// 最后将剩余的‘O’换为‘X’，将之前的‘U’又换回来
public void solve(char[][] board) {
if(board.length == 0){
return;
}
int M = board.length;
int N = board[0].length;
for(int i = 0; i < M; i++){
dfs(i, 0, board);
dfs(i, N - 1, board);
}
for(int j = 0; j < N; j++){
dfs(0, j, board);
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';
}else if(board[i][j] == 'U'){
board[i][j] = 'O';
}
}
}
}
public void dfs(int i, int j, char[][] board){
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O'){
return;
}
board[i][j] = 'U';
for(int[] direct : directs){
dfs(i + direct[0], j + direct[1], board);
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录