# 200 Number of Islands

Input是一個2d的matrix，由0和1組成，1如果彼此相連(上下左右)代表是同一個島嶼，若不相連則為不同的島嶼。回傳整個grid裡共有幾個島嶼。

本來想說這個跟battleship on the board好像差不多，仔細一看其實不一樣，

Battleships can only be placed horizontally or vertically.

Battleships只會是長條形，但Islands可以是各種形狀。

所以就不能單純只看左邊或上面有沒有1來判斷是不是同個島嶼，四個neighbor都要check。

Concept:

掃過grid上的每個element，當讀到1時，找出這個island的所有grid，並設為x表示已經找過，當把整個island都設為x了，counter++

用function exlore()找出island的所有grid，explore會收到整個grid和當下的位置，檢查當下位置上下左右的grid有沒有1，如果有，將它設為x，再explor()，如果上下左右都沒有1了，代表已經找完。

Pseudocode:

Main:
for each element in grid,
    if current element is 1
        counter++
        explore(grid,element,size of grid)
return counter

explore():
int dir list all directions, up, down, left, right
set current element on grid to 'x'
for each neighbor
    get neighbor's index
    if current neighbor is 1
        explore(grid, current neighbor, size of grid)

完整程式碼:

public class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        if (m==0) return 0;
        int n = grid[0].length;
        int count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='1'){
                    count++;
                    explore(grid, i, j, m, n);
                }
            }
        }
        return count;
    }

    public void explore(char[][] grid, int x, int y, int m, int n){
        int dir[][] = {{-1,0},{1,0},{0,-1},{0,1}};
        grid[x][y] = 'x';
        for(int i=0; i<dir.length; i++){
            int a = x + dir[i][0];
            int b = y + dir[i][1];
            if(a>=0 && a<m && b>=0 && b<n){
                if(grid[a][b]=='1'){
                    explore(grid, a, b, m, n);
                }
            }
        }
    }

}