# 200. Number of Islands

{% embed url="<https://mp.weixin.qq.com/s?__biz=MzA5ODk3ODA4OQ==&mid=2648167208&idx=1&sn=d8118c7c0e0f57ea2bdd8aa4d6ac7ab7&chksm=88aa236ebfddaa78a6183cf6dcf88f82c5ff5efb7f5c55d6844d9104b307862869eb9032bd1f&token=1064083695&lang=zh_CN#rd>" %}

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
```

```java

/*
    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);

    }
}
```

加上座標的話, 更清楚

```java
    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,

```java
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;
    }
}
```