时间戳

首页 > 解决方案 > 二维矩阵中 DFS 的时间复杂度（移动是 4 路，每次在当前节点完成 DFS 时我们都会重置访问标志）

time-complexity - 二维矩阵中 DFS 的时间复杂度（移动是 4 路，每次在当前节点完成 DFS 时我们都会重置访问标志）

问题描述

给定一个包含 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^(m*n) 吗？请用你的回答解释扣除。谢谢！

// 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

标签： time-complexitydepth-first-searchspace-complexity

解决方案

该算法本质上是通过尝试从网格左上角到右下角的每条可能路径来工作的，其中每条路径都不允许多次访问网格中的单元格。所以复杂度应该是 O(SARW( m , n )) ，其中 SARW( m , n ) 是网格上从左上角开始到右下角结束的自动回避行走的数量。根据 Wolfram MathWorld的说法，这些被称为自动回避车行走；一个关于数学问题的答案讨论了这样一个事实，即没有确切的计算它们的公式是已知的，但没有提供有关渐近行为的任何信息。

据我所知，增长的顺序也不知道。这个关于 MathOverflow 的答案声称它应该是体积的指数（即 m * n），但没有给出该指数的上界，也没有给出下界，除非基数大于 1。整数在线百科全书对于n = 1 到 27 ， Sequences具有方形情况 (m = n) 的精确数字；我计算了该序列中的数字所暗示的指数基数，并发现它正在增加，但速度越来越慢，因此它可能会稳定在 1.7 或 1.8 左右。这将给出约 的复杂度O(1.8^(mn))，但这是基于经验数据的估计，可能会有所偏差。

推荐阅读