在网格上的DFS中添加返回语句会导致异常

Question

所以这个问题要求打印出在一个mxn网格中从（1,1）到（M，N）的所有路径，以及相同路径的总数。

把M和N都作为输入。M和N是矩形板上的行数和列数。我们的球员从左上角开始，必须到达右下角。在一次移动中，玩家可以水平移动一步（右）或垂直移动一步（下）或斜向移动一步（东南）。

>

编写一个递归函数，返回玩家可以跨板旅行的不同方式的计数。打印返回的值。

编写一个递归函数，打印所有有效路径的移动（void是函数的返回类型）。

Input:

3 3

Output:

VVHH VHVH VHHV VHD VDH HVVH HVHV HVD HHVV HDV DVH DHV DD
13

import java.util.*;
public class Main {
    static int count = 0;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int m = sc.nextInt();
        int n = sc.nextInt();

        dfs(m, n, 0, 0, new int[m][n], "");
        System.out.print("\n" + count);

        sc.close();
    }

    static void dfs(int m, int n, int i, int j, int[][] board, String path) {

        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 1) {
            return;
        }

        board[i][j] = 1;

        if (i == m - 1 && j == n - 1) {
            count++;
            System.out.print(path + " ");
            return; // this line when included does cause problem
        }

        dfs(m, n, i + 1, j, board, path + "V");
        dfs(m, n, i, j + 1, board, path + "H");
        dfs(m, n, i + 1, j + 1, board, path + "D");

        board[i][j] = 0;
    }
}

但当我包含return语句时，输出是：

Input:

3 3

Output:

VVHH 
1

我不明白为什么在我们已经处于董事会最底层的情况下，有返回声明会有不同。

欢迎任何解释。

Answer 1

到达单元格后，您无需对其进行标记。因为只要你向右，向下或向右，你永远不会到达同一个细胞。因此，board[][]是不必要的。

static int count = 0;

static void dfs(int m, int n, int i, int j, String path) {
    if (i < 0 || i >= m || j < 0 || j >= n) {
        return;
    }
    if (i == m - 1 && j == n - 1) {
        count++;
        System.out.print(path + " ");
        return;
    }
    dfs(m, n, i + 1, j, path + "V");
    dfs(m, n, i, j + 1, path + "H");
    dfs(m, n, i + 1, j + 1, path + "D");
}

public static void main(String[] args) {
    dfs(3, 3, 0, 0, "");
    System.out.println();
    System.out.println(count);
}

输出：

VVHH VHVH VHHV VHD VDH HVVH HVHV HVD HHVV HDV DVH DHV DD 
13

Answer 2

问题在于这一行：

board[i][j] = 0;

如果返回时未重置电路板，则结果将不正确。如果您在if语句中返回，则会发生这种情况，因为此行board[i][j]=0 行无法到达。

一个解决方案是将该行添加到if语句中：

if (i == m - 1 && j == n - 1) {
    count++;
    System.out.print(path + " ");
    board[i][j] = 0;
    return;
}