Untitled
unknown
plain_text
3 years ago
1.9 kB
8
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...