grid上DFS添加return语句导致异常

Question

所以问题要求打印 M X N 网格中从 (1,1) 到 (M,N) 的所有路径以及相同路径的总数。

问题陈述

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

写一个递归函数，return计算玩家在棋盘上移动的不同方式。打印值 returned.
编写一个递归函数，打印所有有效路径的移动（void 是函数的 return 类型）。

预计Input/Output：

Input:

3 3

Output:

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

我的JAVA解决方案

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

我无法理解为什么当我们已经在面板的最右下角时使用 return 语句会有所不同。

随时欢迎任何解释。

Answer 1

问题是这里的这一行：

board[i][j] = 0;

如果您 return 不重置电路板，您的结果将不正确。如果您的 if 语句中的 return 会发生这种情况，因为不会到达此行 board[i][j] = 0; 行。

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

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

Answer 2

您不必在到达单元格后对其进行标记。因为只要你向右、向下或向右向下，你就永远不会到达同一个牢房。因此，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

grid上DFS添加return语句导致异常

Adding return statement in DFS on grid causes abnormality

java

recursion

depth-first-search

maze

问题陈述

预计Input/Output：

我的JAVA解决方案