알고리즘/다이나믹 프로그래밍

[B1520] - 내리막길

tongnamuu 2018. 9. 16. 19:01

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

dfs에 메모이제이션을 통해 연산량을 줄여서 풀면 시간초과가 안납니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
using namespace std;
int a[501][501];
int d[501][501];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int m, n;
int ans = 0;
int dfs(int xnode, int ynode)
{
    if (xnode == m - 1 && ynode == n - 1)
    {
        return 1;
    }
    if (d[xnode][ynode]!=-1)
        return d[xnode][ynode];
    d[xnode][ynode] = 0;
    for (int k = 0; k < 4; k++)
    {
        int nx = xnode + dx[k];
        int ny = ynode + dy[k];
        if (nx >= 0 && nx < m&&ny >= 0 && ny < n&&a[nx][ny] < a[xnode][ynode])
        {
            d[xnode][ynode]+=dfs(nx, ny);
        }
    }
    return d[xnode][ynode];
}
int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
            d[i][j] = -1;
        }
    }
    ans=dfs(0, 0);
    printf("%d\n", ans);
}
cs


저작자표시 비영리 변경금지 (새창열림)