1520 내리막 길

1520 내리막 길

1. 목적지( n, m ) 이면 1반환

2. 한번도 방문하지 않은곳이면 dfs탐색

3. 방문했던 곳이면 d[x][y] 반환

4. ( 1, 1 ) 부터 시작.

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, m;
int map[502][502];
int d[502][502];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int dfs(int x,int y) {
    if (x == n && y == m) {
        return 1;
    }
 
    //(x,y)가 한번도 방문하지 않았을 경우만 탐색
    if (d[x][y] == -1) {
        d[x][y] = 0;
 
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
 
            if (map[ax][ay] == 0) continue;
 
            if (map[x][y] > map[ax][ay]) {
                d[x][y] += dfs(ax, ay);
            }
        }
    }
    return d[x][y];
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
            d[i][j] = -1;
        }
    }
 
    d[n][m] = 1;
    dfs(1, 1);
 
    cout << d[1][1] << endl;
}