# 1905. Count Sub Islands
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/count-sub-islands/
## 思路
遍历grid2
每次找到一个新的island bfs遍历完岛（都设成visited）
如果岛里面有一个点不在grid1里面
就说明现在的岛不是subIsland
## Code

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m=grid2.length, n=grid2[0].length;
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid2[i][j]==1){
                    if(bfs(grid1, grid2, i, j)) ans++;
                }
            }
        }
        return ans;
    }
    private boolean bfs(int[][] grid1, int[][] grid2, int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        boolean isSubIsland = true;
        if(grid1[x][y]==0) isSubIsland = false;
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.isEmpty()){
            int[] curr = q.poll();
            for(int[] dir:dirs){
                int nextX = curr[0]+dir[0];
                int nextY = curr[1]+dir[1];
                if(nextX>=0 && nextX<grid2.length && nextY>=0 && nextY<grid2[0].length && grid2[nextX][nextY]==1){
                    if(grid1[nextX][nextY]==0) isSubIsland = false;
                    grid2[nextX][nextY]=-1;
                    q.add(new int[]{nextX, nextY});
                }
            }
        }
        return isSubIsland;
    }
}