반응형
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
BFS -> 시간 초과
DFS + DP로 풀어야 함
dp[i][j] = -1 : 방문 안함
|
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
|
#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int m, n;
int arr[501][501];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
int dp[501][501];
int dfs(int x, int y) {
if (x == (m - 1) && y == (n - 1))
return 1;
// -1: 방문 안 한 상태
if (dp[x][y] == -1) {
// 0: 방문 한 상태
dp[x][y] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (arr[nx][ny] < arr[x][y])
dp[x][y] += dfs(nx, ny);
}
}
}
return dp[x][y];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(dp, -1, sizeof(dp));
cin >> m >> n;
rep(i, m) {
rep(j, n)
cin >> arr[i][j];
}
cout << dfs(0, 0);
}
|
cs |
반응형