2D矩阵中DFS的时间复杂度（移动是4种方式，每次在当前节点上完成DFS时我们都会重置访问标志）

Question

给出带有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

Answer 1

该算法本质上是通过尝试从网格的左上角到右下角的所有可能路径来工作的，其中每个路径都不允许多次访问网格中的单元。因此，复杂度应约为O（SARW（m，n）），其中SARW（m，n）是网格上开始的self-avoiding walks的数目在左上角，在右下角结束。根据Wolfram MathWorld，这些被称为self-avoiding rook walks。 an answer to a question on Mathematics.SE讨论了这样一个事实：尚无确切的公式来计算它们，但没有提供有关渐近行为的任何信息。

据我所知，增长的顺序也不知道。 This answer on MathOverflow声称它在体积中应该是指数的（即m * n），但在该指数的基数上没有上限，除了基数大于1以外，没有下限。 Online Encyclopedia of Integer Sequences的方格数字（m = n）；我计算了该序列中的数字所隐含的指数基数，发现它在增加，但是速度越来越慢，因此可以稳定在1.7或1.8左右。这将带来大约n = 1 to 27的复杂度，但这是基于经验数据的估计，可能会有所不同。]