200. Number of Islands

1, 如果加上斜的也可以。dfs加四种情况
dfs(grid,i-1,j-1);
dfs(grid,i+1,j+1);
dfs(grid,i-1,j+1);
dfs(grid,i+1,j-1);
2, 不让改变原有的input，我就说那就建一个相同size的2d boolean array。
或者visited[][]设成global
3, 转换为union find或者bfs，bfs解法：https://discuss.leetcode.com/topic/12230/c-bfs-solution-may-help-you
4, dfs，有可能stack overflow

public class Solution {
    
    private int m;
    private int n;
    private char[][] visit;
    public int numIslands(char[][] grid) {
        int count=0;
        m=grid.length;
        if(m==0) return 0;
        n=grid[0].length;
        visit=new char[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                visit[i][j]=grid[i][j];
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(visit[i][j]=='1'){
                    dfs(visit,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i<0||j<0||i>=m||j>=n||grid[i][j]=='0') return;
        grid[i][j]='0';
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
    }
}

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

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