SRM576 DIV2 -Level2
問題
①２次元の配列が与えられる。
②配列には”Ｘ”で表わされる床が存在する。一番下は全て床になっている。
③また、コインのある座標が与えられる。
④ユーザは一番下の床からスタートし、任意の長さの梯子を使って床へ移動し、コインを獲得する。
⑤このとき、必要となる最小の梯子の長さを求める。
解き方
問題の性質から、２分探索が思い浮かぶ。
ただ高さの上限が少ないので、単純に小さい数からループさせてもよい。
Ｃｈａｌｌｅｎｇｅのポイント
また、移動の判定とキューへのスタックがかなりの計算量になるので、
一度行ったことのある例外判定をきちんと行う必要がある。
たとえばコード中の以下など。
if(check[i][j]==1)continue;
コード
class ArcadeManao {
public: int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
int h=level.size(),w=level[0].size();
int check[h][w];
int low=0,high=h;
for(int L=0;L<100;L++){
queue <pair <int, int> > q;
q.push(make_pair(coinRow-1,coinColumn-1));
int flag=0;
FORE(i,0,h)FORE(j,0,w)check[i][j]=0;
while(!q.empty()){
int i=q.front().first;
int j=q.front().second;
q.pop();
if(check[i][j]==1)continue;
if(i==h-1){
flag=1;
break;
}
while(j-1>=0 && level[i][j-1]=='X')j--;
for(int cur=j;level[i][cur]=='X';cur++){
check[i][cur]=1;
for(int up=i;up>=max(0,i-L);up--)
if(check[up][cur]==0 && level[up][cur]=='X')q.push(make_pair(up,cur));
for(int down=i;down<=min(h-1,i+L);down++)
if(check[down][cur]==0 && level[down][cur]=='X')q.push(make_pair(down,cur));
}
}
if(flag==1)return L;
}
return h-1;
}
};
public: int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
int h=level.size(),w=level[0].size();
int check[h][w];
int low=0,high=h;
for(int L=0;L<100;L++){
queue <pair <int, int> > q;
q.push(make_pair(coinRow-1,coinColumn-1));
int flag=0;
FORE(i,0,h)FORE(j,0,w)check[i][j]=0;
while(!q.empty()){
int i=q.front().first;
int j=q.front().second;
q.pop();
if(check[i][j]==1)continue;
if(i==h-1){
flag=1;
break;
}
while(j-1>=0 && level[i][j-1]=='X')j--;
for(int cur=j;level[i][cur]=='X';cur++){
check[i][cur]=1;
for(int up=i;up>=max(0,i-L);up--)
if(check[up][cur]==0 && level[up][cur]=='X')q.push(make_pair(up,cur));
for(int down=i;down<=min(h-1,i+L);down++)
if(check[down][cur]==0 && level[down][cur]=='X')q.push(make_pair(down,cur));
}
}
if(flag==1)return L;
}
return h-1;
}
};
