백준 1890번 C++

#include<iostream>

#include<cstring>

using namespace std;

int n;

int arr[101][101];

long long ans[101][101];

long long calway() {

ans[0][0] = 1;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (ans[i][j] != 0 && i != n-1 && i+arr[i][j]< n) {

ans[i + arr[i][j]][j] += ans[i][j];

}

if (ans[i][j] != 0 && j!= n-1 && j+arr[i][j] < n ) {

ans[i][j + arr[i][j]] += ans[i][j];

}

}

}

return ans[n - 1][n - 1];

}

int main(void) {

cin >> n;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> arr[i][j];

}

}

memset(ans, 0, sizeof(ans));

cout << calway();

return 0;

}