[BOJ] 1520 : 내리막 길

#include <stdio.h>

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int n, m, a[505][505], d[505][505];

int dfs(int x, int y) {
	if (x == n && y == m) return 1;
	if (~d[x][y]) return d[x][y];
	d[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (a[nx][ny] && a[nx][ny] < a[x][y]) d[x][y] += dfs(nx, ny);
	}
	return d[x][y];
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
		scanf("%d", &a[i][j]), d[i][j] = -1;

	printf("%d\n", dfs(1, 1));

	return 0;
}