Найти кластеры в многомерном массиве Java

Question

Мне нужно найти количество кластеров с учетом многомерного массива 0 и 1. Кластер определяется единицами, которые соседствуют в направлениях вверх, вниз, влево или вправо НЕ диагональ . Это означает, что следующий многомерный массив имеет один кластер:

01000
01000

И следующий имеет два:

00100
00010

Я написал код (см. МОЙ КОД ниже), но после компиляции и тестирования с В нескольких случаях использования он не может дать непротиворечивый точный ответ:

Когда выполняется следующее, он должен дать следующие результаты:

RUN:

package org.example;

public class App 
{
    public static void main( String[] args )
    {
        FindCluster findCluster = new FindCluster();
        FindCluster findCluster0 = new FindCluster();
        FindCluster findCluster1 = new FindCluster();
        FindCluster findCluster2 = new FindCluster();
        // Attempt 1

        int myArr[][] = {
                {1, 1, 0, 0, 1},
                {0, 1, 0, 0, 1},
                {1, 0, 0, 1, 1},
                {0, 0, 0, 0, 0},
                {1, 0, 1, 1, 0}
        };

        int numOfClusters = findCluster.findNumberOfClusters(5, 5, myArr);
        System.out.println("The number of clusters found in your Array is: " + numOfClusters);

        // Attempt 2

        int myArr0[][] = {
                {1, 0, 1, 0, 1},
                {0, 1, 1, 0, 1},
                {1, 1, 0, 1, 0},
                {0, 0, 1, 0, 1},
                {1, 0, 1, 1, 0}
        };

        int numOfClusters0 = findCluster0.findNumberOfClusters(5, 5, myArr0);
        System.out.println("The number of clusters found in your Array is: " + numOfClusters0);

        // Attempt 3

        int myArr1[][] = {
                {1, 1, 0, 1, 1},
                {0, 1, 0, 0, 1},
                {1, 0, 1, 0, 1},
                {0, 0, 1, 0, 1},
                {0, 0, 1, 1, 0}
        };

        int numOfClusters1 = findCluster1.findNumberOfClusters(5, 5, myArr1);
        System.out.println("The number of clusters found in your Array is: " + numOfClusters1);

        // Attempt 4

        int myArr2[][] = {
                {1, 1, 0, 1, 1},
                {0, 1, 1, 0, 1},
                {1, 0, 1, 0, 1},
                {0, 0, 1, 0, 1},
                {1, 0, 1, 1, 1}
        };

        int numOfClusters2 = findCluster2.findNumberOfClusters(5, 5, myArr2);
        System.out.println("The number of clusters found in your Array is: " + numOfClusters2);
    }
}

Ожидаемые результаты:

The number of clusters found in your Array is: 5
The number of clusters found in your Array is: 7
The number of clusters found in your Array is: 4
The number of clusters found in your Array is: 3

Фактические результаты:

The number of clusters found in your Array is: 5
The number of clusters found in your Array is: 6
The number of clusters found in your Array is: 3
The number of clusters found in your Array is: 4

МОЙ КОД:

package org.example;

public class FindCluster {

    private int clusters = 0;

    private boolean gridCheckArr[][] = null;

    private int gridClusterArr[][] = null;

    public void setGridCheckArr(int rows, int columns) {
        this.gridCheckArr = new boolean[rows][columns];
    }

    public void setGridClusterArr(int gridClusterArr[][]) { this.gridClusterArr = gridClusterArr; }

    public void setGridCheckInitialValues(){
        for(int r = 0;r < gridCheckArr.length; r++){
            for(int c = 0; c < gridCheckArr[r].length; c++){
                gridCheckArr[r][c] = false;
            }
        }
    }

    public Integer findNumberOfClusters(int rows, int columns, int grid[][]) {

        // Using a method to set a grid to check if location has been visited
        setGridCheckArr(rows, columns);
        // Using a method to set the initial values to false for the grid being checked
        setGridCheckInitialValues();
        // Using a method to set the the classes grid to the grid passed to the method called
        setGridClusterArr(grid);
        // Using a method that performs the checks and computation of the clusters
        gridCheck();

        return this.clusters;
    }

    public void gridCheck() {
        for(int r = 0; r < gridCheckArr.length; r++) {
            for(int c = 0; c < gridCheckArr[r].length; c++) {
                if(r == 0 && c == 0){
                    checkFirstRowBeginning(r, c);
                } else if (r == 0 && c == gridCheckArr[r].length - 1) {
                    checkFirstRowEnd(r, c);
                } else if ( r == 0 && c > 0) {
                    checkFirstRow(r, c);
                } else if (r == gridCheckArr.length - 1 && c == 0) {
                    checkLastRowBeginning(r, c);
                } else if (r == gridCheckArr.length -1 && c == gridCheckArr[r].length -1) {
                    checkLastRowEnd(r, c);
                } else if (r == gridCheckArr.length -1 && c > 0) {
                    checkLastRow(r, c);
                } else if (r > 0 && c == 0) {
                    checkRowBeginning(r, c);
                } else if (r > 0 && c == gridCheckArr[r].length -1) {
                    checkRowEnd(r, c);
                } else if (r > 0 && c > 0) {
                    checkRow(r, c);
                } else {
                    System.out.println("Oops something went wrong trying to find a grid check!!!!");
                }
            }
        }
    }

    public void checkFirstRow(int row, int column) { // checks Left, Right, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row + 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at First Row case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkFirstRowBeginning(int row, int column) { // checks Right, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row + 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at First Row Beginning case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkFirstRowEnd(int row, int column) { // checks Left, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row + 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at First Row End case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkRow(int row, int column) { // checks Left, Right, Up, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row - 1][column] != true && this.gridCheckArr[row + 1][column] != true) {
                    if((this.gridCheckArr[row - 1][column - 1] != true && this.gridClusterArr[row][column - 1] != 1) && (this.gridCheckArr[row - 1][column + 1] != true && this.gridClusterArr[row][column + 1] != 1) && (this.gridCheckArr[row + 1][column - 1] != true && this.gridClusterArr[row][column - 1] != 1) && (this.gridCheckArr[row + 1][column + 1] != true && this.gridClusterArr[row][column + 1] != 1)) {
                        this.clusters++;
                    }
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at a Row case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkRowBeginning(int row, int column) { // checks Right, Up, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row - 1][column] != true && this.gridCheckArr[row + 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at a Row Beginning case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkRowEnd(int row, int column) { // checks Left, Up, Down
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row - 1][column] != true && this.gridCheckArr[row + 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at a Row End case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkLastRow(int row, int column) { // checks Left, Right, Up
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row - 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at Last Row case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkLastRowBeginning(int row, int column) { // checks Right, Up
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column + 1] != true && this.gridCheckArr[row - 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at Last Row Beginning case not able to be handled array index value is: " + arrIndexValue);
        }
    }

    public void checkLastRowEnd(int row, int column) { // checks  Left, Up
        int arrIndexValue = this.gridClusterArr[row][column];
        switch(arrIndexValue) {
            case 0:
                break;
            case 1:
                this.gridCheckArr[row][column] = true;
                if(this.gridCheckArr[row][column - 1] != true && this.gridCheckArr[row - 1][column] != true) {
                    this.clusters++;
                }
                break;
            default:
                System.out.println("Oops something went wrong when trying to check grid at Last Row End case not able to be handled array index value is: " + arrIndexValue);
        }

    }
}

Я понимаю, почему происходит сбой, когда я вручную отслеживаю его в определенных SCENAR ios. Тем не менее, я застрял на поиске алгоритма, который решит проблему. Например, в Попытке 4 для myArr2

int myArr2[][] = {
                {1, 1, 0, 1, 1},
                {0, 1, 1, 0, 1},
                {1, 0, 1, 0, 1},
                {0, 0, 1, 0, 1},
                {1, 0, 1, 1, 1}
        };

Количество кластеров сначала увеличивается с 0 до 1 для первого идентифицированного 1 в первом столбце (индекс [0] [0]). Затем, когда он достигает третьего 1 , указанного в первом столбце (индекс [0] [3]), моя логическая проверка снова увеличивает количество кластеров на 1 . Это неверно, поскольку в действительности оно связано в кластере с первыми двумя 1 , указанными ранее в первой строке (индексы [0] [0] и [0] [1]), как определено, если вы следуете смежные 1 во всем двумерном массиве. Как создать логический алгоритм для реализации этого?

Любой, кто может улучшить мой код, чтобы исправить ошибки или предоставить лучшее / более эффективное решение с объяснением того, как / почему он работает лучше?

Answer 1

• Чтобы найти количество кластеров, вам придется рекурсивно двигаться во всех 4 направлениях, применяя подход поиск в глубину в первый раз, когда вы находите ячейку со значением 1.

• Способ работы DFS - помечать все ячейки, которые соединены 4, в одном кадре. Итак, мы получаем кластер. Мы не посещаем одну и ту же ячейку при поиске других кластеров, поскольку помечаем эти ячейки как посещенные.

• Чтобы пометить ячейку как посещенную, мы изменим ее значение на -1 и позже восстановите его до 1, сделав его эффективным.

Фрагмент:

public class Main{
    public static void main(String[] args) {
        int myArr[][] = {
                {1, 1, 0, 0, 1},
                {0, 1, 0, 0, 1},
                {1, 0, 0, 1, 1},
                {0, 0, 0, 0, 0},
                {1, 0, 1, 1, 0}
        };


        System.out.println(findNumClusters(myArr));
    }

    private static int findNumClusters(int[][] arr){
        int num_clusters = 0;

        for(int i=0;i<arr.length;++i){
            for(int j=0;j<arr.length;++j){
                if(arr[i][j] == 1){
                    dfs(arr,i,j,arr.length,arr[0].length);
                    num_clusters++;
                }
            }
        }

        // restore all ones
        for(int i=0;i<arr.length;++i){
            for(int j=0;j<arr.length;++j){
                if(arr[i][j] == -1) arr[i][j] = 1;
            }
        }

        return num_clusters;
    }

    private static void dfs(int[][] arr,int x,int y,int rows,int cols){
        if(x < 0 || x == rows || y < 0 || y == cols || arr[x][y] != 1) return;
        arr[x][y] = -1; // marking a cell as visited(will be restored later)
        dfs(arr,x-1,y,rows,cols);
        dfs(arr,x+1,y,rows,cols);
        dfs(arr,x,y-1,rows,cols);
        dfs(arr,x,y+1,rows,cols);
    }
}

Демонстрация: https://www.onlinegdb.com/HJLJR56eU