200. Number of Islands

LeetCode 例题精讲 | 12 岛屿问题：网格结构中的 DFS微信公众平台

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

/*
    use flood fill, use dfs to traverse all island, and mark vistied 
    
    time complexity: O(n*m), space complexity: O(1), n is grid's height, m is grid's width

*/
class Solution {
    private int n; //grid's height
    private int m; //grid's width
    public int numIslands(char[][] grid) {
        n = grid.length;
        if (n == 0) return 0;
        
        m = grid[0].length;
        
        int count = 0;
        
        // loop grid[][]
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') { //if touch the land, do dfs traverser
                    dfs(grid, i, j);
                    count++; //find island, count++
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        // terminator
        // out of bound or it's water
        if (i < 0 || j < 0 || i >= n || j >=m || grid[i][j] == '0') return;
        
        //drill down
        // an islan to be sinked, visited, island becomes water
        grid[i][j] = '0';
        
        // traverse all surrouding area
        dfs(grid, i+1, j);
        dfs(grid, i, j+1);
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);

    }
}

加上座標的話, 更清楚

    public static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private int n; // graph's height
    private int m; // width

    public int numIslands(char[][] grid) {
        n = grid.length;
        if (n == 0) return 0;

        m = grid[0].length;

        int count = 0; // the count of island

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') { // an island's start
                    dfs(grid, i, j); //run dfs, run through an island
                    count++; // count of island++
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;

        grid[i][j] = '0'; // mark visited

        for (int d[] : directions) {
            dfs(grid, i + d[0], j + d[1]); // toward different directions...
        }

    }

use visited, dont modify origin grid value(no flood fill)

因為在某些題目是不能改值的 , 這時候還是要用 visited 來標記走過了

使用 visited,

class Solution {
    private int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
      
        int res = 0;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);            
                    res++;
                }
            }
        }
        return res;
    }
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        if (!inArea(grid, i, j) || visited[i][j] || grid[i][j] == '0') {
            return;
        }
        visited[i][j] = true;
        for (int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1], visited);
        }
    }
    
    private boolean inArea(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >=0 && j < grid[0].length;
    }
}