점프

#include <iostream> #include <vector> #include <algorithm> typedef long long ll; std::vector<std::vector<int> >board; std::vector<std::vector<ll> >dp; std::vector<std::pair<int, int> >dir; int N; ll ans; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> N; board.resize(N, std::vector<int>(N)); size_t _N = N; for (size_t i = 0 ; i < _N ; i++) for (size_t j = 0 ; j < _N ; j++) std::cin >> board[i][j]; dp.resize(N, std::vector<ll>(N)); dir = {{1, 0}, {0, 1}}; ans = 0; } ll dfs(int y, int x) { if (dp[y][x] > 0) return (dp[y][x]); if (dp[y][x] == -1) return (0); if (y == N - 1 && x == N - 1) return (1); for (size_t i = 0 ; i < dir.size(); i++) { int d_y = y + dir[i].first * board[y][x]; int d_x = x + dir[i].second * board[y][x]; if (d_y >= N || d_x >= N || (d_y == y && d_x == x)) continue; dp[y][x] += dfs(d_y, d_x); } if (dp[y][x] == 0) dp[y][x] = -1; return (dp[y][x] != -1 ? dp[y][x] : 0); } void solve() { if (board[0][0] < N) { ans = dfs(0, board[0][0]); ans += dfs(board[0][0], 0); } } void print_val() { std::cout << ans << std::endl; } int main() { input(); solve(); print_val(); return (0); }