これはほぼ同じ問題を考えたことがあったので余裕だった。
https://community.topcoder.com/stat?c=problem_statement&pm=15623&rd=17617
問題
ある建物にいくつかのコインが配置されており、それを回収したい。
この建物は横方向は任意に移動できるが、縦方向は2か所に設置された垂直な梯子を使ってしか移動できない。
また、この梯子は上にしか移動できない。
全コインを回収する最短移動距離を求めよ。
解法
コインの置いてある各縦座標について、コインを回収して両梯子に戻る最短経路を順次計算していこう。
コインを回収するには、その縦座標にある最も左と最も右のコインを回収すればよいので、移動経路は以下のいずれか。
- 左梯子→左端コイン→右端コイン→左梯子
- 左梯子→左端コイン→右端コイン→右梯子
- 右梯子→左端コイン→右端コイン→左梯子
- 右梯子→左端コイン→右端コイン→右梯子
- 左梯子→右端コイン→左端コイン→左梯子
- 左梯子→右端コイン→左端コイン→右梯子
- 右梯子→右端コイン→左端コイン→左梯子
- 右梯子→右端コイン→左端コイン→右梯子
なお、縦座標0のみ開始位置が梯子ではないことと、もっとも高い位置ではコインを回収して終了なので、梯子に戻らなくてよい点に注意。
class TwoLadders { public: long long minSteps(int sx, int lx1, int lx2, vector <int> X, vector <int> Y) { map<ll,pair<ll,ll>> M; int i; FOR(i,X.size()) { if(M.count(Y[i])==0) { M[Y[i]]={(ll)X[i],(ll)X[i]}; } else { M[Y[i]].first=min(M[Y[i]].first,(ll)X[i]); M[Y[i]].second=max(M[Y[i]].second,(ll)X[i]); } } if(M.size()==1 && M.begin()->first==0) { ll x1=M[0].first,x2=M[0].second; return min(abs(sx-x1)+abs(x2-x1),abs(sx-x2)+abs(x2-x1)); } ll L,R; if(M.count(0)) { ll x1=M[0].first,x2=M[0].second; L=min(abs(sx-x1)+abs(x2-x1)+abs(x2-lx1),abs(sx-x2)+abs(x2-x1)+abs(x1-lx1)); R=min(abs(sx-x1)+abs(x2-x1)+abs(x2-lx2),abs(sx-x2)+abs(x2-x1)+abs(x1-lx2)); } else { L=abs(sx-lx1); R=abs(sx-lx2); } FORR(m,M) { if(m.first==0) continue; if(m.first==M.rbegin()->first) continue; ll x1=m.second.first,x2=m.second.second; ll PL=L,PR=R; L=min({PL+abs(x1-lx1)+abs(x2-x1)+abs(lx1-x2),PL+abs(x2-lx1)+abs(x2-x1)+abs(lx1-x1),PR+abs(x1-lx2)+abs(x2-x1)+abs(lx1-x2),PR+abs(x2-lx2)+abs(x2-x1)+abs(lx1-x1)}); R=min({PL+abs(x1-lx1)+abs(x2-x1)+abs(lx2-x2),PL+abs(x2-lx1)+abs(x2-x1)+abs(lx2-x1),PR+abs(x1-lx2)+abs(x2-x1)+abs(lx2-x2),PR+abs(x2-lx2)+abs(x2-x1)+abs(lx2-x1)}); } ll x1=M.rbegin()->second.first,x2=M.rbegin()->second.second; ll ret=min({L+abs(x1-lx1)+abs(x2-x1),L+abs(x2-lx1)+abs(x2-x1),R+abs(x1-lx2)+abs(x2-x1),R+abs(x2-lx2)+abs(x2-x1)}); return ret+M.rbegin()->first; } }
まとめ
コーナーケース対策が面倒だな。