「1002 : Extraordinary Grid I」の編集履歴（バックアップ）一覧に戻る
1002 : Extraordinary Grid I
普段はもっとスマートなコードを書くのですが、今回は良い方法を思いつかなかったので力ずくでメモ化探索するコードを書きました。
これが試験なら最低点、ぎりぎり○といったところです。
1 最小移動距離を求める問題ですが、この時司書は進む時、左から右へか上下へ移動するのはあっても右から左へ戻ることはありません。
２ ある交差点にいる時、今までたどってきた経路のうち最短距離以外の経路は無視してもよい。
この性質を利用しメモ化します。
1列ずつ処理します。
ある列にいる時、横道３行全てから上下移動して本を返し次の列のｎ(1～３)行目に移動します。ｎ行目同士で最短距離を比較し一番短いものを残す。
この時今いる行*次の行での位置という３行*３行の９通りの移動が考えられます。
状況としては返す本がある無しの4通り、３６通りの状況が考えられます。
この縦一列の本を処理する時の３６通り全ての最短移動距離を手作業で求めてコード化しました。
4行やｎ行と一般になった時でも解ける手法で解くのが１００点とするならこのコードは２０点程度でしょうか。
#include <stdio.h>
#include <algorithm>
void setMap(int);
int memo[3][20004];/*司書が一列ずつ棚を処理した時、３行ｎ列目までの最短距離のメモカ*/
int map[2][20004];/*通路一列ずつ返す本があるかないかに関する記述、図でいえば上下２列に分かれている*/
int main()
{
int m,n;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&n);
setMap(n);
}
}
void setMap(int n){
char t;
int x,y;
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);
map[y][x]=0;/*棚の初期化*/
}
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);/*ある列に返す本があるかどうかあるなら1を設定する*/
scanf(" %c",&t);
map[y][(x+1)/2]+=((t=='Y') ? 1:0);
}
memo[0][0]=0;
memo[1][0]=1;
memo[2][0]=2;
/*棚を左から右へ一列ずつ処理し、次の列へ行った時最短距離だけを残していく*/
for(int i=0;i<n;i++){
memo[0][i+1]=memo[1][i+1]=memo[2][i+1]=100000000;
if(map[0][i]>0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]>0 && map[1][i]==0){
memo[0][i+1]=std::min(memo[0][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]==0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+2,memo[2][i+1]);
}else{
memo[0][i+1]=std::min(memo[0][i]+1,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+1,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+1,memo[2][i+1]);
}
}
/*最終列だけ特別な処理が必要*/
if(map[0][n]>0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else if(map[0][n]>0 && map[1][n]==0){
memo[0][n]+=1;
memo[1][n]+=1;
}else if(map[0][n]==0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else{
memo[1][n]+=1;
}
memo[2][n]+=2;
int ans;
ans=std::min(memo[0][n],memo[1][n]);
ans=std::min(ans,memo[2][n]);
printf("%d\n",ans);
}
