[BaekJoon][1520] 내리막 길

BAEKJOON ONLINE JUDGE

1520 내리막 길

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

#include <stdio.h>
#include <string.h>
 
int n, m;
int map[510][510];
int dp[510][510];
 
int solve(int y, int x)
{
    int *res = &dp[y][x];
    int i;
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    int sum = 0;
 
    if (*res != -1)            return *res;
    if (map[y][x] < 0)    return 0;
 
    for (i = 0; i < 4; i++) {
        if (map[dy[i] + y][dx[i] + x] > map[y][x])
            *res += solve(dy[i] + y, dx[i] + x);
    }
 
    return *res;
}
 
int main()
{
    int i, j;
 
    memset(dp, -1, sizeof(dp));
    memset(map, -1, sizeof(map));
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    dp[1][1] = 1;
    printf("%d\n", solve(n, m));
 
    return 0;
}