내리막 길

• 목적지에 도착했다면 true를 return해서 목적지까지 갔던 길을
• right_way는 목적지로 갈수 있는 방법의 수를 가지고 있는다
• bad_point는 가봤자 의미 없는 지점을 저장한다

import java.util.Scanner;

public class Main {
	static int M;
	static int N;
	static int[][] arr;
	static boolean[][] check;
	static int[][] right_way;
	static boolean[][] bad_point;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		M = sc.nextInt();
		N = sc.nextInt();

		arr = new int[M][N];

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		check = new boolean[M][N];
		right_way = new int[M][N];
		bad_point = new boolean[M][N];

		right_way[M - 1][N - 1] = 1;

		ham(0, 0);

		System.out.println(count);
	}

	static int count = 0;

	static boolean ham(int r, int c) {
		if (r == M - 1 && c == N - 1) {
			count++;
			return true;
		}
		check[r][c] = true;
		boolean return_check = false;

		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];
			if (nr < 0 || nc < 0 || nr >= M || nc >= N || arr[nr][nc] >= arr[r][c] || check[nr][nc]
					|| bad_point[nr][nc])
				continue;
			if (right_way[nr][nc] != 0) {
				return_check = true;
				right_way[r][c] += right_way[nr][nc];
				count += right_way[nr][nc];
				continue;
			} else if (ham(nr, nc)) {
				return_check = true;
				right_way[r][c] += right_way[nr][nc];
			}
		}
		check[r][c] = false;
		if (!return_check) {
			// 갈 필요가 없는 곳을 체크해준다
			bad_point[r][c] = true;
		}
		return return_check;
	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
}