読者です 読者をやめる 読者になる 読者になる

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;
}