ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1002 Extraordinary Grid I

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1002

図書館の本棚に本をすべて戻すのにかかる最短の移動数を求める問題です。


・解法
動的計画法(DP)で解くことができます。

int dp[10001(横の座標)][3(縦の座標)]
のような配列を用意します。
左の方向には移動しないことが分かっているので、あとは実装すればよいです。

下のソースコードはif文大量に使っていてあんまり良いコードではないかも知れません。


ソースコード

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

static const int INF = (1 << 29);

int N;
int dp[10001][3];
char book[10001][2];

int solve(){
  for(int j = 0 ; j < 3 ; j++) dp[0][j] = j;
   
  for(int i = 1 ; i <= N ; i++){
    if(book[i-1][0]=='N' && book[i-1][1]=='N'){
      dp[i][0] = min(dp[i-1][0]+1, min(dp[i-1][1]+2, dp[i-1][2]+3));
      dp[i][1] = min(dp[i-1][0]+2, min(dp[i-1][1]+1, dp[i-1][2]+2));
      dp[i][2] = min(dp[i-1][0]+3, min(dp[i-1][1]+2, dp[i-1][2]+1));
    }
    else if(book[i-1][0]=='Y' && book[i-1][1]=='Y'){
      dp[i][0] = min(dp[i-1][0]+4, min(dp[i-1][1]+3, dp[i-1][2]+3));
      dp[i][1] = min(dp[i-1][0]+3, min(dp[i-1][1]+3, dp[i-1][2]+3));
      dp[i][2] = min(dp[i-1][0]+3, min(dp[i-1][1]+3, dp[i-1][2]+4));
    }
    else if(book[i-1][0]=='Y'){
      dp[i][0] = min(dp[i-1][0]+2, min(dp[i-1][1]+2, dp[i-1][2]+3));
      dp[i][1] = min(dp[i-1][0]+2, min(dp[i-1][1]+2, dp[i-1][2]+3));
      dp[i][2] = min(dp[i-1][0]+3, min(dp[i-1][1]+3, dp[i-1][2]+4));
    }
    else if(book[i-1][1]=='Y'){
      dp[i][0] = min(dp[i-1][0]+4, min(dp[i-1][1]+3, dp[i-1][2]+3));
      dp[i][1] = min(dp[i-1][0]+3, min(dp[i-1][1]+2, dp[i-1][2]+2));
      dp[i][2] = min(dp[i-1][0]+3, min(dp[i-1][1]+2, dp[i-1][2]+2));
    }
    else return INF;
      
    if(i==N){
      if(book[i][0]=='N' && book[i][1]=='N'){
        dp[i][0] = min(dp[i][0], min(dp[i][1]+1, dp[i][2]+2));
      }
      else if(book[i][0]=='Y' && book[i][1]=='Y'){
        dp[i][0] = min(dp[i][0]+3, min(dp[i][1]+2, dp[i][2]+2));
      }
      else if(book[i][0]=='Y'){
        dp[i][0] = min(dp[i][0]+1, min(dp[i][1]+1, dp[i][2]+2));
      }
      else if(book[i][1]=='Y'){
        dp[i][0] = min(dp[i][0]+3, min(dp[i][1]+2, dp[i][2]+2));
      }
      else return INF;
    }
      
    else{
      dp[i][0] = min(dp[i][0], min(dp[i][1]+1, dp[i][2]+2));
      dp[i][1] = min(dp[i][1], min(dp[i][0]+1, dp[i][2]+1));
      dp[i][2] = min(dp[i][2], min(dp[i][0]+2, dp[i][1]+1));
    }
  }
   
  return dp[N][0];
}

int main(){
  int T;
  cin >> T;
  while(T--){
    cin >> N;
    for(int j = 0 ; j < 2 ; j++){
      for(int i = 0 ; i <= N ; i++){
        if(i==0 || i==N)cin >> book[i][j];
        else{
          char a,b;
          cin >> a >> b;
          if(a=='Y' || b=='Y')book[i][j] = 'Y';
          else book[i][j] = 'N';
        }
      }
    }
    cout << solve() << endl;
  }
  return 0;
}