Untitled
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...