SRM563 DIV2 -Level2

<問題>
①2次元のフィールドが与えられる。
②フィールドにはランダムな数の障害物と、2つのコインが置かれている。
③プレイヤーは上下左右の操作をすることができ、1度の操作で選んだ方向に1マスだけ2つのコインを動かせる。動く先に障害物がある場合は動かない。
④コインが動いた時、フィールドから外れた場合はコインが落ちる。
⑤このとき、コインを1つだけ落としたいときの最小の操作回数を返す。
 ただし、操作回数が10回を超えた時はー1を返す。

<解き方>
動的計画法で最小の操作回数を求める。
単純なシミュレーションですが、いかに簡単に書いて間違いを少なくするかが
ポイントだと思います。

-1となる例外の処理を再帰関数で書いた時には処理がうまくいかなかったので、
例外の処理はメイン関数で行う方がよさそう。

また、vectorを渡す時には &bのようにしてあげないと
処理がおかしくなるので注意。

<コード>
class CoinsGameEasy {

public:

int f(int turn,int x1,int y1,int x2,int y2,vector<string>& b){
if(turn>10)return turn;

int ret=11,w=b[0].size(),h=b.size();
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
FORE(i,0,4){
int flag=0;
int tx1=x1+dx[i],ty1=y1+dy[i],tx2=x2+dx[i],ty2=y2+dy[i];
if(tx1<0 || tx1>=w || ty1<0 || ty1>=h)flag++;
if(tx2<0 || tx2>=w || ty2<0 || ty2>=h)flag++;
if(flag==1)return turn+1;
if(flag==2)continue;
if(b[ty1][tx1]=='#')tx1=x1,ty1=y1;
if(b[ty2][tx2]=='#')tx2=x2,ty2=y2;
ret=min(ret,f(turn+1,tx1,ty1,tx2,ty2,b));
}
return ret;
}

int minimalSteps(vector<string> board) {
int x[2],y[2],idx=0,ret;

FORE(i,0,board.size()){
FORE(j,0,board[0].size()){
if(board[i][j]=='o'){
x[idx]=j;
y[idx++]=i;
}
}
}
ret=f(0,x[0],y[0],x[1],y[1],board);
return ret>10 ? -1 : ret;
}

};
このエントリーをはてなブックマークに追加