AOJ0203 A New Plan of Aizu Ski Resort
解法
典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。
あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。
自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, 斜めから進入するのを1 と分けて3次元配列にしてみたけど、意味はあったのだろうか。
反省
障害物やジャンプ台の判定を別関数に分けて見やすくした。結構迷わず書けたと思ったのにずっとWAでおかしいと思ったら、入力の高さと幅が逆だった。
先日の立命合宿で作って持ってきてた人いたけど、自分も有りがちなミスの確認表みたいなの作ろうと思う。
#include <bits/stdc++.h> using namespace std; int grid[30][30]; inline bool isAtObstacle(int x, int y) { return grid[y][x] == 1; } inline bool isAtSkiJump(int x, int y) { return grid[y][x] == 2; } int main() { int n, m; while(cin >> m >> n && n) { fill(grid[0], grid[0]+900, 0); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin >> grid[i][j]; } } int dp[30][30][2] = {{{}}}; for(int j=0; j<m; j++) { if(grid[0][j]==0) { dp[0][j][0] = 1; } } int extra = 0; for(int i=0; i<n-1; i++) { for(int j=0; j<m; j++) { // there is no case that skier is at obstacle. if(isAtObstacle(j, i)) continue; // A skier is at a ski jump. if(isAtSkiJump(j, i)) { if(i+2 > n-1) extra += dp[i][j][0]; else { if(isAtObstacle(j, i+2)) continue; dp[i+2][j][0] += dp[i][j][0]; } } // skiing without jump. else { // from the upper left if( j-1 >= 0 && !isAtObstacle(j-1, i+1) && !isAtSkiJump (j-1, i+1) ) { dp[i+1][j-1][1] += dp[i][j][0] + dp[i][j][1]; } // from the above if( !isAtObstacle(j, i+1) ) { dp[i+1][j][0] += dp[i][j][0] + dp[i][j][1]; } // from the upper right if( j+1 < m && !isAtObstacle(j+1, i+1) && !isAtSkiJump (j+1, i+1) ) { dp[i+1][j+1][1] += dp[i][j][0] + dp[i][j][1]; } } } } int ans = 0; for(int i=0; i<m; i++) { ans += dp[n-1][i][0] + dp[n-1][i][1]; } cout << ans + extra << endl; } return 0; }