Untitled

 avatar
unknown
plain_text
2 years ago
1.9 kB
2
Indexable
import java.util.*;

public class Main {
    static int count = 0;

    static int countAllPath(int n, int m) {
        boolean[][] visited = new boolean[n][m]; // initialize visited array
        recur(0, 0, n, m, visited);
        return count;
    }

    public static void recur(int i, int j, int n, int m, boolean[][] visited) {
        if (i == n - 1 && j == m - 1) {
            count++;
            return;
        }
        if (i >= n || j >= m || i < 0 || j < 0 || visited[i][j]) {
            return;
        }
        visited[i][j] = true; // mark current cell as visited
        for (int jumps = 1; jumps <= n - 1 - i; jumps++) { // down
            recur(i + jumps, j, n, m, visited);
        }
        for (int jumps = 1; jumps <= i; jumps++) { // up
            recur(i - jumps, j, n, m, visited);
        }
        for (int jumps = 1; jumps <= m - 1 - j; jumps++) { // right
            recur(i, j + jumps, n, m, visited);
        }
        for (int jumps = 1; jumps <= j; jumps++) { // left
            recur(i, j - jumps, n, m, visited);
        }
        for (int jumps = 1; jumps <= Math.min(m - 1 - j, n - 1 - i); jumps++) { // right down
            recur(i + jumps, j + jumps, n, m, visited);
        }
        for (int jumps = 1; jumps <= Math.min(m - 1 - j, i); jumps++) { // right up
            recur(i - jumps, j + jumps, n, m, visited);
        }
        for (int jumps = 1; jumps <= Math.min(i, j); jumps++) { // left up
            recur(i - jumps, j - jumps, n, m, visited);
        }
        for (int jumps = 1; jumps <= Math.min(j, n - 1 - i); jumps++) { // left down
            recur(i + jumps, j - jumps, n, m, visited);
        }
        visited[i][j] = false; // mark current cell as unvisited
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(countAllPath(n, m));
    }
}
Editor is loading...