[数据结构与算法]深度优先搜索中等 NC109 岛屿数量

NC109 岛屿数量

描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
示例1
输入：[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
返回值：3

代码：

• 需要遍历每一个节点才能知道全部岛屿的数量。
• 建立一个相同大小的数组标记已探明的岛屿，每次遍历到一个’1’,标记与他连接的所有’1’，记录到预数量的变量+1。
• 当遇到’0’或者已探明的岛屿则跳过。

import java.util.*;
public class Solution {
    public int solve (char[][] grid) {
        // write code here
        int len = grid[0].length;
        int width = grid.length;
        int sum = 0;
        boolean [][] sign = new boolean[width][len];
        for(int i = 0; i < width; i++){
            for(int j = 0; j < len; j++){
                if(sign[i][j] == true || grid[i][j] == '0'){
                    continue;
                }
                islandDFS(grid,sign,i,j);
                sum++;
            }
        }
        return sum;
    }

    public void islandDFS(char[][] arr, boolean[][] sign, int a, int b){
        if(a < 0 || a == arr.length || b < 0 || b == arr[0].length){
            return;
        }
        if(arr[a][b] == '0' || sign[a][b] == true){
            return;
        }
        sign[a][b] = true;
        islandDFS(arr,sign,a+1,b);
        islandDFS(arr,sign,a-1,b);
        islandDFS(arr,sign,a,b+1);
        islandDFS(arr,sign,a,b-1);
        return;
    }
}