BOJ 1520 내리막 길

Link

DFS & Memoization

…밖에 코멘트할 것이 없는 것 같아요

코드 (C++)

#include <iostream>

using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, a[600][600], d[600][600];

int dfs(int x, int y) {
if (x == n && y == m) {
return 1;
}
if (~d[x][y]) {
return d[x][y];
}
d[x][y] = 0;
for (int i = 0; i < 4; i++) {
int now_x = x + dx[i], now_y = y + dy[i];
if (a[now_x][now_y] && a[now_x][now_y] < a[x][y]) {
d[x][y] += dfs(now_x, now_y);
}
}
return d[x][y];
}

int main(int argc, const char *argv[]) {
cin.tie(nullptr);
ios::sync_with_stdio(false);

cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
d[i][j] = -1;
}
}
cout << dfs(1, 1) << endl;

return 0;
}
Total views

댓글

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×