题解 | 岛屿数量

import java.util.*;

//思想：利用BFS判断遍历相邻节点，并设为已访问，遍历整个地图，不断的找未访问并且为陆地的节点，然后对他进行BFS；
//时间复杂度：O(m*n),因为双重for循环和bfs是线性叠加的
//空间复杂度：O(m*n)
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here
        int r=grid.length;
        int c=grid[0].length;
        int[][] v=new int[r][c]; //访问数组
        int ans=0;
            for(int i=0;i<r;i++){
                for(int j=0;j<c;j++){
                    if(grid[i][j]=='1'&&v[i][j]==0){ //找陆地点
                        bfs(v,grid,i,j);
                        ++ans;
                    }
                }
            }
        return ans;
    }
    int[][] d=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public void bfs(int v[][],char[][] grid,int x,int y){
        Deque<int[]> q=new ArrayDeque<>();
        int r=grid.length;
        int c=grid[0].length;
        q.offer(new int[]{x,y});
        v[x][y]=1;
        while(!q.isEmpty()){
            int[] t=q.poll();
            int xt=t[0];
            int yt=t[1];
            for(int i=0;i<d.length;i++){
                int tx=xt+d[i][0];
                int ty=yt+d[i][1];
                if(tx>=0&&tx<r&&ty>=0&&ty<c&&grid[tx][ty]=='1'&&v[tx][ty]==0){ //边界判断
                    v[tx][ty]=1;
                    q.offer(new int[]{tx,ty});
                }
            }
        }
    }
}