[数据结构与算法]DFS—LC200. 岛屿数量

LC200. 岛屿数量

LC200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：

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

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。
最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int res=0;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;

    }

    void dfs(char[][] grid,int i,int j){
        int m=grid.length;
        int n=grid[0].length;

        if(i<0||j<0||i>=m||j>=n||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
    }
}

拓展：求形状不同的岛屿的数量

LC 694

思路： hashset保存相对路径，用集合去重。
岛屿左上角的那个坐标设为(x, y)，然后岛屿内的每个元素都减去这个值，存成集合来判断两个集合是否相等
最后返回的set的大小，即为岛屿的种类

class Solution {
    public int numDistinctIslands(int[][] grid) {
      //用set储存岛屿，set不能包括重复的岛屿
        Set<List<List<Integer>>> islands = new HashSet<>();
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                List<List<Integer>> island = new ArrayList<>();
                if (grid[i][j] == 1){
                    dfs(grid,i, j, i, j, island);
                    islands.add(island);                   
                }
            }
        }
        return islands.size();
    }
    private void dfs(int[][] grid, int row, int col, int dx, int dy, List<List<Integer>> island){
        //exclude the illegal situation
        if (row < 0 || row >= grid.length || col<0 || col >= grid[0].length){
            return;
      }
        if (grid[row][col] !=1){
          return;
      }
        //add the coordinate to the list
        island.add(Arrays.asList(dx-row, dy-col));
        //mark the visited land
        grid[row][col] = 2;
        
        //Search the for direction
        dfs(grid, row - 1, col, dx, dy, island);
        dfs(grid, row + 1, col, dx, dy, island);
        dfs(grid, row, col - 1, dx, dy, island);
        dfs(grid, row, col + 1, dx, dy, island);
    }
}