BOJ[백준] - 1520 - 내리막 길

Posted by ceyx
2017. 7. 15. 01:44 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/1520

 

 

 

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
#include <stdio.h>
 
int dp[501][501], a[501][501], N, M, i, j;
int nx[] = { 1,-1,0,0 }, ny[] = { 0,0,1,-1 };
 
int solve(int x, int y)
{
   int ret = 0;
   if(x == 0 || y == 0)
      return 0;
   if(x == N && y == M)
      return 1;
   if(dp[x][y] != -1)
      return dp[x][y];
   for(int i = 0; i < 4; i++)
      if(a[x][y] > a[x + nx[i]][y + ny[i]])
         ret += solve(x + nx[i], y + ny[i]);
   return dp[x][y] = ret;
}
 
int main()
{   
   scanf("%d %d"&N, &M);
   for(i = 1; i <= N; i++)
      for(j = 1; j <= M; j++)
         scanf("%d"&a[i][j]),dp[i][j]=-1;
 
   printf("%d", solve(1,1));
   return 0;
}
cs