矩阵中岛数量问题

名字是乱打的

发布于 2022-05-13 01:46:57

68200

代码可运行

运行总次数：0

代码可运行

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？举例： 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 这个矩阵中有三个岛。 不分布式的思路: 遍历矩阵,碰到为1的则岛数+1,并且递归的更改该点和其上下左右数值为1的点的值为2 分布式的思路: 将非常非常大的矩阵均匀的分给各个机器进行处理各个机器收集自己机器上岛的数量和边界信息;统计总岛的数量,利用并查集合并边界,如果两个边界的根是可合并的,减一个岛的数量

不分布式代码

package com.algorithm.practice.matrix;

public class IsLand {

    public static int countIslands(int[][] m) {
        if (m == null || m[0] == null) {
            return 0;
        }
        int N = m.length;//行数
        int M = m[0].length;//列数
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1) { //遍历找出每个是1的位置
                    res++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return res;
    }

    public static void infect(int[][] m, int i, int j, int N, int M) { //将m矩阵(i,j)位置周边的1都改为2
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
            return;//如果(i,j)不在矩阵中,退出
        }
        m[i][j] = 2;
        //将该点的上下左右为1的数继续改为2并递归
        infect(m, i + 1, j, N, M);
        infect(m, i - 1, j, N, M);
        infect(m, i, j + 1, N, M);
        infect(m, i, j - 1, N, M);
    }

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

        int[][] m2 = {
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m2));

    }

}