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.

CodePudding user response：

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

CodePudding user response：

You don't have to mark the path you have taken once. Because as long as you go to right, down or right down, you will never follow the same path. Therefore, board[][] is unnecessary.

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

output:

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