Adding return statement in DFS on grid causes abnormality

Question

So the question asked to print all the paths to reach from (1,1) to (M,N) in an M X N grid and total numbers of ways for the same.

Problem Statement

Take as input M and N, both numbers. M and N is the number of rows and columns on a rectangular board. Our player starts in top-left corner of the board and must reach bottom-right corner. In one move the player can move 1 step horizontally (right) or 1 step vertically (down) or 1 step diagonally (south-east).

• Write a recursive function which returns the count of different ways the player can travel across the board. Print the value returned.

• Write a recursive function which prints moves for all valid paths across the board (void is the return type for function).

Expected Input/Output:

Input:

3 3

Output:

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

My JAVA Solution

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;
    }
}

But When I include the return statement then the ouput is:

Input:

3 3

Output:

VVHH 
1

I am not able to understand why does it make difference to have the return statement when we are already at the right-most bottom of the board.

Any explanations are always welcome.

Answer 1

The problem is this line here:

board[i][j] = 0;

If you return without resetting the board, your result will be incorrect. This will happen if your return in your if statement, since this line board[i][j] = 0; line wont be reached.

A solution would be to add that line to the if statement:

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