题解 | #岛屿数量#

#岛屿数量#解题思路：按行遍历矩阵，遇到‘1’则使用广度优先移除已经参与计数的岛屿。使用递归删除左右上下相邻的grid[i][j]=='1'的格子即可。此方法时间复杂度o(n^2)。

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