ネタができるまで,暇な時にこれまで解いてきたAtCoderの過去問を上げていくことにしました.
問題文
イルカは x 軸正方向を右、 y 軸正方向を上とする 2 次元座標平面にいます。 イルカは現在点(sx, sy) にいて、 1 秒あたり上下左右に距離 1 だけ進むことができます。 このとき、移動前と移動後の x 座標、 y 座標はともに整数でなければなりません。 イルカはここから sx < tx と sy < ty を満たす点 (tx, ty) に行き、その後点 (sx, sy) に戻り、また点 (tx, ty) に行き、その後点 (sx, sy) に戻ります。 このとき、イルカは点 (sx, sy) と点 (tx, ty) を除いて、途中で同じ座標を複数回通らないように移動しなければなりません。 このような条件を満たすイルカの最短経路を 1 つ求めてください。
制約
−1000 ≦ sx < tx ≦ 1000, −1000 ≦ sy < ty ≦ 1000, sx, sy, tx, ty は整数である。
方針
目的地までの1往復目は最短経路,2往復目は最短経路の外を迂回する経路とする.目的地までの最短経路は,まずは目的地のx座標まで移動して,その後目的地のy座標まで移動する.帰路は逆周りで帰ってくる.
2往復目を考えます.1往復目において,出発地点の1マス上と1マス右は既に通った経路となるので通れません.そのため,2往復目は必ず,1マス下と1マス左を,往路と復路で使う必要があります.このような経路を考えると,以下の図のような経路を考えることができます.
これをc++で書いたものが以下のようになります.
#include <iostream> using namespace std; int main(){ int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty; int R,L,U,D; R = tx-sx; L = R; U = ty-sy; D = U; for (int i = 0; i < R; i++) cout << "R"; for (int i = 0; i < U; i++) cout << "U"; for (int i = 0; i < L; i++) cout << "L"; for (int i = 0; i < D; i++) cout << "D"; cout << "D"; for (int i = 0; i < R+1; i++) cout << "R"; for (int i = 0; i < U+1; i++) cout << "U"; cout << "L"; cout << "U"; for (int i = 0; i < L+1; i++) cout << "L"; for (int i = 0; i < D+1; i++) cout << "D"; cout << "R"; return 0; }