随笔记录

算法——统计岛数量

2022-3-3 diaba 算法

package com.jiucaiyuan.net.question;

/**
 * 统计岛数量
 * 【问题】一个矩阵中只有0和1两个数值，每个位置都可以和自己的上、下、左、右四个位置相连，
 * 如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
 * 【进阶】
 * 如何设计一个并行算法解决这个问题(一张地图，点特别多，需要统计时，并行解决会更快些)
 * <p>
 * P12 11.基础提升 有序表、并查集等     00:03
 *
 * @Author jiucaiyuan  2022/3/2 23:58
 * @mail services@jiucaiyuan.net
 */
public class CountIslands {
    /**
     * 统计岛的个数
     * 时间复杂度O(row*col)
     *
     * @param arr
     * @return
     */
    public static int countIslands(int[][] arr) {
        if (arr == null || arr.length < 1 || arr[0].length < 1) {
            return 0;
        }
        int result = 0;
        int row = arr.length;
        int col = arr[0].length;
        //两个for，从左往右，从上往下，把所有节点处理一遍
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //如果是1，岛数加1，和他相连的都感染
                if (arr[i][j] == 1) {
                    result++; //岛数+1
                    infect(arr, i, j, row, col);  //已经树的岛数标记为2（感染）
                }
            }
        }
        return result;
    }

    /**
     * 检查(i,j)位置是否进行感染，并继续向周围感染
     *
     * @param arr 二维数组表示矩阵
     * @param i   检查(i,j)位置是否进行感染，并继续向周围感染
     * @param j   检查(i,j)位置是否进行感染，并继续向周围感染
     * @param row 矩阵行数
     * @param col 矩阵列数
     */
    private static void infect(int[][] arr, int i, int j, int row, int col) {
        if (i < 0 || j < 0 || i >= row || j >= col || arr[i][j] != 1) {
            return;
        }
        //原来是1，感染修改为2
        arr[i][j] = 2;
        infect(arr, i - 1, j, row, col);
        infect(arr, i + 1, j, row, col);
        infect(arr, i, j - 1, row, col);
        infect(arr, i, j + 1, row, col);
    }

    private static void print(int[][] arr) {
        System.out.println("-----------------------------------------");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {0, 0, 0, 1, 0, 0, 1, 0},
                {0, 1, 1, 1, 0, 0, 1, 0},
                {0, 0, 0, 1, 0, 0, 1, 0},
                {0, 1, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 1, 0},
                {0, 0, 1, 1, 0, 0, 1, 0},
                {0, 0, 0, 1, 0, 0, 1, 0},
        };
        print(arr);
        System.out.println(countIslands(arr));
        print(arr);
        int[][] arr2 = {
                {0, 0, 0, 1, 0, 0, 1, 0},
                {0, 1, 1, 1, 0, 0, 1, 0},
        };
        print(arr2);
        System.out.println(countIslands(arr2));
        print(arr2);
        int[][] arr3 = {
                {0, 1, 0, 1, 0, 0, 1, 0},
        };
        print(arr3);
        System.out.println(countIslands(arr3));
        print(arr3);
    }

}