Node.js) 백준 1520번: 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const [N, M] = input.shift();

const dp = Array.from(Array(N), () => Array(M).fill(-1));
dp[N - 1][M - 1] = 1;

const dx = [0, 0, 1, -1];
const dy = [-1, 1, 0, 0];

function dfs(x, y) {
	if (dp[x][y] != -1) {
		return dp[x][y];
	}
	let cnt = 0;
	for (let k = 0; k < 4; k++) {
		const nx = x + dx[k];
		const ny = y + dy[k];
		if (nx < 0 || nx >= N || ny < 0 || ny >= M || input[nx][ny] >= input[x][y]) continue;

		cnt += dfs(nx, ny);
	}

	dp[x][y] = cnt;
	return cnt;
}

console.log(dfs(0, 0));