Используя DFS (сначала глубина), найдите плотность блоков, плотность которых превышает% X - PullRequest
Новая
       52

Используя DFS (сначала глубина), найдите плотность блоков, плотность которых превышает% X

0 голосов
/ 12 июня 2018

В моей работе (некоторые матричные вычисления) я застрял с проблемой, как показано ниже: 

matrix (NxN):   
          xxxx------------------
          xxxx------------------
          ----xxx-x-------------
          ----xx--x-------------
          ---------x--x---------
          ---------xxxx---------
                   xxxx---------
            ......................

enter image description here

У меня есть 2D прил.матрица имеет паттерн блочных диаграмм (как показано выше).Каждый блок может быть плотным (100%) или разреженным (0,01-5%).Как найти размер блока (begin_row, Being_col, End_row, End_col), а также их соответствующую плотность (mod (E) / mod (V)), используя эти вспомогательные матрицы и используя поиск по графику (DFS)?

Я уверен, что есть простой способ найти блоки и плотность.Я ищу любую идею или псевдокод, я был бы очень признателен за ваше время.

1 Ответ

0 голосов
/ 20 июня 2018

Вы можете пересечь диагональ к карте, где каждый блок начинается и заканчивается.Поперечное сечение можно сделать с помощью dfs или простого циклаЗатем ключ определяет конец блока.С «полными» блоками все просто, как продемонстрировано в методе isCorner.Этот метод должен быть изменен, чтобы учесть дыры.

    //test data
    public static int[][] intArray = {
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {1,  1,  0,  0,  0,  0,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  1,  1,  1,  1,  0,  0,  0},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1},
        {0,  0,  0,  0,  0,  0,  1,  1,  1}
    };

    public static void main(String[] args) {

        mapBlock();
    }

    //traverse diagonal to find block start and block end
    private static void mapBlock() {
        //todo check that matrix is nxn

        int[] origin = {0,0}; //dfs start point
        //traverse diagonal
        for(int rowIndex =0; rowIndex < intArray.length ; rowIndex ++) {
            if(isCorner(rowIndex, rowIndex)) { //diagonal row and col index are equal
                int[] target = {rowIndex, rowIndex}; //dfs target
                block(origin, target);
                origin = new int[]{rowIndex+1, rowIndex+1};
            }
        }
    }

    //is intArray[row Index][column Index] a corner 
    private static boolean isCorner(int rowIndex, int colIndex) {

        //corner must be on diagonal
        if(rowIndex != colIndex ) {
            return false;
        }

        //if last row and col it is a corner
        if(((rowIndex+1) == intArray.length) && ((colIndex+1) == intArray.length))  {
            return true;
        }

        //if left and bottom neighbors are empty - it is a corner
        //todo if you blocks have holes this criteria needs to change
        if((intArray[rowIndex+1][colIndex] == 0) && (intArray[rowIndex][colIndex+1] == 0) ) {
            return true;
        }

        return false;
    }

    private static void block(int[] origin, int[] target) {

        System.out.println("block from " +Arrays.toString(origin)+
                " to "+Arrays.toString(target));
        //todo store sub array 
    }

Вывод:

блок из [0, 0] в [1, 1]блок от [2, 2] до [5, 5]блок от [6, 6] до [8, 8]

(проверить онлайн )

...