Временная сложность DFS в 2D-матрице (перемещение выполняется в 4 направлениях, и мы сбрасываем флаг посещения при каждом завершении DFS на текущем узле) - PullRequest
Новая
       76

Временная сложность DFS в 2D-матрице (перемещение выполняется в 4 направлениях, и мы сбрасываем флаг посещения при каждом завершении DFS на текущем узле)

1 голос
/ 13 января 2020

Учитывая матрицу направления с L, R, U, D, в любой точке вы можете двигаться в направлении, которое записано над ячейкой [i, j]. Мы должны указать минимальное количество модификаций, чтобы достичь от [0, 0] до [N - 1, M - 1]. 

    Example :-
    R R D
    L L L
    U U R

Answer is 1, we can modify cell [1, 2] from L To D.

Какова будет временная сложность для (следующего) решения DFS? Обратите внимание, как мы сбрасываем флаг посещения каждый раз, когда исследуем узел. Это 4 ^ (м * н)? Пожалуйста, объясните вывод своим ответом. Спасибо! 

// minimumModification(arr, 0, 0, new boolean[arr.length][arr[0].length])       
private static int minimumModification(char[][] arr, int i, int j, boolean[][] visited)
{
    if(i<0 || j<0 || i>=arr.length || j>= arr[0].length || visited[i][j])
        return max;

    if(i == arr.length-1 && j == arr[0].length-1)
        return 0;

    visited[i][j] = true;
    int min = max;

    int right = minimumModification(arr, i, j+1, visited);
    int left = minimumModification(arr, i, j-1, visited);
    int down = minimumModification(arr, i+1, j, visited);
    int up = minimumModification(arr, i-1, j, visited);

    if(right != max && arr[i][j] != 'R')
        right++;
    if(left != max && arr[i][j] != 'L')
        left++;
    if(down != max && arr[i][j] != 'D')
        down++;
    if(up != max && arr[i][j] != 'U')
        up++;

    min = Math.min(min, right);
    min = Math.min(min, left);
    min = Math.min(min, down);
    min = Math.min(min, up);

    visited[i][j] = false;
    return min;
}

static final int max = Integer.MAX_VALUE;

источник вопроса: Leetcode https://leetcode.com/discuss/interview-question/476340/google-onsite-min-modifications

1 Ответ

0 голосов
/ 18 января 2020

Алгоритм по сути работает, пробуя каждый возможный путь от верхнего левого до нижнего правого угла сетки, где каждому пути не разрешено посещать ячейку в сетке более одного раза. Таким образом, сложность должна быть около O (SARW ( m , n )), где SARW ( m , n ) - это число самостоятельные прогулки по сетке, которые начинаются в верхнем левом углу и заканчиваются в нижнем правом. Они известны как самостоятельные прогулки по ладьям согласно Wolfram MathWorld; ответ на вопрос о Mathematics.SE обсуждает тот факт, что точная формула для их подсчета не известна, но не дает никакой информации об асимптотическом поведении c.

Как насколько я могу судить, порядок роста тоже неизвестен. В этом ответе по MathOverflow утверждается, что он должен быть экспоненциальным по объему (т. Е. M * n), но не дается верхняя граница для основания этой экспоненты и нет нижней границы, за исключением того, что основание больше 1 * Онлайн-энциклопедия целых последовательностей содержит точные числа для квадратного регистра (m = n) для n = от 1 до 27 ; Я вычислил, какая экспоненциальная база будет подразумеваться числами в этой последовательности, и обнаружил, что она увеличивается, но все медленнее и медленнее, поэтому она может выровняться где-то в районе 1,7 или 1,8. Это дало бы сложность около O(1.8^(mn)), но это оценка, основанная на эмпирических данных, которые могут быть далеко.

...