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);
}
}