题解 | #岛屿数量#

import java.util.*;


public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */
    public int solve (char[][] grid) {
        // write code here
        int  m = grid.length;
        int  n = grid[0].length;

        //记录岛屿数量
        int count = 0 ;
        for (int i = 0 ; i < m ; i++) {
            for (int j = 0 ; j < n ; j++) {
                //判断当前位置字符是否为1
                //如果是1
                if (grid[i][j] == '1') {

                    count++;
                    //方法1: dfs 一条路走到黑 把所有能到达的坐标如果是1都变成0

                    //dfs(grid,i,j);
                    //方法2: bfs 从被选中的点开始扩散 把该点周边的1都变成0

                    bfs(grid, i, j);
                }
            }
        }

        return count;
    }
    void dfs(char[][] grid, int i, int j) {
        //dfs 结束条件 当数组越界时 或者 到达 '0' 时 终止遍历
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ||
                grid[i][j] == '0')
            return;
        //将当前遍历到的'1' 变为 '0'
        grid[i][j] = '0';
        //向上遍历
        dfs(grid, i - 1, j);
        //向下遍历
        dfs(grid, i + 1, j);
        //向左遍历
        dfs(grid, i, j - 1);
        //向右遍历
        dfs(grid, i, j + 1);

    }

    void bfs(char[][] grid, int i, int j) {

        int len = grid[0].length;
        
        //将当前遍历到的'1' 变为 '0'
        grid[i][j] = '0';
        //与dfs一条路走到底不同 bfs 是要把周边能到达的点都要变成 '0'
        Queue<Integer> queue = new LinkedList<>();
        //由于 队列中只能存储一种数据 而 地址信息由两位 因此使用code转换
        int code = i * len + j;
        queue.add(code);
        while(!queue.isEmpty()){
            //取出队首数据 
            int index = queue.poll();
            
            int x = index/len;
            int y = index%len;

            if(x > 0 && x <= grid.length -1 && grid[x-1][y] == '1')
            {
                 grid[x-1][y] = '0';
                queue.add((x-1)*len+y);
            }
            if(x >= 0 && x < grid.length -1 && grid[x+1][y] == '1')
            {
                grid[x+1][y] = '0';
                queue.add((x+1)*len+y);
            }
            if(y > 0 && y <= len -1 && grid[x][y-1] == '1')
            {
                grid[x][y-1] = '0';
                queue.add(x*len+y-1);
            }
            if(y >= 0 && y < len-1 && grid[x][y+1] == '1')
            {
                grid[x][y+1] = '0';
                queue.add(x*len+y+1);
            }
        }

    }
}