图论系列(dfs岛屿) 9/26

一、统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

输入：grid = [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]
输出：2

思路：

当grid[x][y]=0的时候，我们开始遍历；对每个节点进行dfs搜索

如果该节点正好是第一行第一列或者最后一行最后一列，那么直接返回false；(因为已经到达边界了，就无法被包围了)

如果该节点正好是1并且没有被访问过，返回true，周围是1，满足被包围的条件。

向四个方向递归调用dfs，只有同时满足true，才能说明是被包围的。

代码：

class Solution {boolean[][] visited;public int closedIsland(int[][] grid) {int res = 0;visited = new boolean[grid.length][grid[0].length];for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 0 && !visited[i][j]) {if(dfs(grid,i,j))res++;}}}return res;}public boolean dfs(int[][] grid, int x, int y) {if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1)return false;if (grid[x][y] == 1||visited[x][y])return true;visited[x][y] = true;boolean up = dfs(grid, x - 1, y);boolean down = dfs(grid, x + 1, y);boolean left = dfs(grid, x, y - 1);boolean right = dfs(grid, x, y + 1);return up && down && left && right;}
}

二、被围绕的区域(和飞地的数量类似)

题意:

给定一个m*n的矩阵，由'X'、'O'组成。如果O的四周被X包围，那么O就要改成X；

思路：

1.出现在矩阵边缘的O定不会被包围，首先寻找未被包围的‘O’,通过dfs边缘的O，寻找连通子块。

        for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if ((i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) && board[i][j] == 'O') {dfs(board, i, j);}}}

2.然后剩下的O就是被包围的，将他们标记成X；最后将连通子块标记成O

        for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == 'O')board[i][j] = 'X';}}for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == 'A')board[i][j] = 'O';}}}

代码:

class Solution {boolean[][] visited;public void solve(char[][] board) {visited = new boolean[board.length][board[0].length];for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if ((i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1) && board[i][j] == 'O') {dfs(board, i, j);}}}for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == 'O')board[i][j] = 'X';}}for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == 'A')board[i][j] = 'O';}}}public void dfs(char[][] board, int x, int y) {if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 || 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);}
}

三、统计子岛屿

给定两个岛屿，看岛屿b中的岛屿是不是岛屿a中的子岛屿。

思路1(叠加法)：

因为1是陆地，所以将两个岛屿中的1相加起来，如果为2，这就是他们重叠的陆地。

如果值为2的岛屿中含有值为1的陆地，那么他就不是子岛屿；

如果都是2，说明是子岛屿。

1.叠加两个岛屿的陆地

        for (int i = 0; i < grid2.length; i++) {for (int j = 0; j < grid2[0].length; j++) {if (grid2[i][j] == 1)grid2[i][j] += grid1[i][j];}}

2.然后在叠加后中寻找值都为2的岛屿

    public boolean dfs(int[][] grid, int x, int y) {if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1||visited[x][y])return true;if (grid[x][y] !=2)return grid[x][y]==0;visited[x][y] = true;boolean up = dfs(grid, x - 1, y);boolean down = dfs(grid, x + 1, y);boolean left = dfs(grid, x, y - 1);boolean right = dfs(grid, x, y + 1);return up&&down&&left&&right;}

代码：

class Solution {boolean[][] visited;public int countSubIslands(int[][] grid1, int[][] grid2) {visited = new boolean[grid1.length][grid1[0].length];for (int i = 0; i < grid2.length; i++) {for (int j = 0; j < grid2[0].length; j++) {if (grid2[i][j] == 1)grid2[i][j] += grid1[i][j];}}int res = 0;for (int i = 0; i < grid2.length; i++) {for (int j = 0; j < grid2[0].length; j++) {if (grid2[i][j] == 2 && !visited[i][j]) {if(dfs(grid2,i,j))res++;}}}return res;}public boolean dfs(int[][] grid, int x, int y) {if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1||visited[x][y])return true;if (grid[x][y] !=2)return grid[x][y]==0;visited[x][y] = true;boolean up = dfs(grid, x - 1, y);boolean down = dfs(grid, x + 1, y);boolean left = dfs(grid, x, y - 1);boolean right = dfs(grid, x, y + 1);return up&&down&&left&&right;}
}

思路2(淹没法):

在相同的位置处，如果矩阵2中是陆地，矩阵1中是海洋。那么这一定不是子岛屿，直接将该陆地的连通子块都淹没掉。

淹没完不是子岛屿的岛屿，剩下的就是子岛屿的岛屿。再次寻找即可

代码：

class Solution {boolean[][] visited;public int countSubIslands(int[][] grid1, int[][] grid2) {visited = new boolean[grid1.length][grid1[0].length];for (int i = 0; i < grid2.length; i++) {for (int j = 0; j < grid2[0].length; j++) {if(grid2[i][j]==1&&grid1[i][j]==0){dfs(grid2,i,j);}}}int res = 0;for (int i = 0; i < grid2.length; i++) {for (int j = 0; j < grid2[0].length; j++) {if (grid2[i][j] == 1 && !visited[i][j]) {dfs(grid2,i,j);res++;}}}return res;}public void dfs(int[][] grid, int x, int y) {if(x<0||y<0||x>grid.length-1||y>grid[0].length-1||visited[x][y]){return ;}if(grid[x][y]==0)return;visited[x][y]=true;grid[x][y]=0;dfs(grid,x-1,y);dfs(grid,x+1,y);dfs(grid,x,y+1);dfs(grid,x,y-1);}
}