力扣labuladong——一刷day75

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

图论，深搜还有广搜都只是手段

一、力扣200. 岛屿数量（广搜）

class Solution {
    int[][] arr = new int[][]{
        {0,1},
        {0,-1},
        {1,0},
        {-1,0}
    };
    boolean[][] flag;
    public int numIslands(char[][] grid) {
        int count = 0;
        flag = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(!flag[i][j] && grid[i][j] == '1'){
                    count ++;
                    bfs(grid, i, j);
                }
            }
        }
        return count;
    }
    
    public void bfs(char[][] grid, int x, int y){
        Deque<int[]> deq = new ArrayDeque<>();
        deq.offerLast(new int[]{x,y});
        flag[x][y] = true;
        while(!deq.isEmpty()){
            int size = deq.size();
            for(int i = 0; i < size; i ++){
                int[] cur = deq.pollFirst();
                for(int j = 0; j < 4; j ++){
                    int curX = cur[0] + arr[j][0];
                    int curY = cur[1] + arr[j][1];
                    if(curX < 0 || curY < 0 || curX >= grid.length || curY >= grid[0].length || grid[curX][curY] == '0' || flag[curX][curY]){
                        continue;
                    }
                    flag[curX][curY] = true;
                    deq.offerLast(new int[]{curX,curY});
                }
            }
        }
    }
}

二、力扣200. 岛屿数量（深搜）

class Solution {
    int[][] arr = new int[][]{
        {0,1},
        {0,-1},
        {1,0},
        {-1,0}
    };
    boolean[][] flag;
    public int numIslands(char[][] grid) {
        int count = 0;
        flag = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(!flag[i][j] && grid[i][j] == '1'){
                    count ++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid, int x, int y){
        if(flag[x][y]){
            return;
        }
        flag[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int curX = x + arr[i][0];
            int curY = y + arr[i][1];
            if(curX < 0 || curY < 0 || curX >= grid.length || curY >= grid[0].length || grid[curX][curY] == '0'){
                continue;
            }
            dfs(grid, curX, curY);
        }
    }
}