草体にぼ日記

だらだらと

ABC051C Back and Forth

ABC051C Back and Forth

(niboshi time 30minutes)

問題

提出AC

int main()
{
    cout <<setprecision(10);
    point S , G;
    cin >>S.x >> S.y >> G.x >> G.y;
    vector<string> road(4,"");
    
    int X , Y ;
    X = G.x - S.x;
    Y = G.y - S.y;
    //まず、ずっと→ の次に 上で行く経路J
    //G.x - S.x 個 、右に移動する
    rep(i,X){
        road[0] += 'R';
    }
    rep(i,Y){
        road[0] += 'U';
    }
    //一つ道順が求まった
 
    //二つ目は戻る道（遠回りで戻る）
    //まず右に一歩、下に Y+1  回 → 次に、左に X+1 回 最後に上に一回
    //road[1]
    road[1] += 'R';
    rep(i,Y+1){
        road[1] +='D';
    }
    rep(i,X+1){
        road[1] += 'L';
    }
    road[1] += 'U';
 
    //次はずっと上からの右
    rep(i,Y){
        road[2] +='U';
    }
    rep(i,X) road[2] +='R';
 
    //最後は、戻る道順上1左X+1 下Y+1 右1
    road[3] += 'U';
    rep(i,X+1) road[3] += 'L';
    rep(i,Y+1) road[3] += 'D';
    road[3] +='R';
 
    for(auto x : road){
        cout << x ;
    }
    cout << endl;
}

これなんですがついでにWAコードもはって置きます（一部抜粋）

//二つ目は戻る道（遠回りで戻る）
    //まず右に一歩、下に Y+1  回 → 次に、左に X+1 回 最後に上に一回
    //road[1]
    road[1] += 'R';
    rep(i,Y+1){
        road[1] +='U';
    }
    rep(i,X+1){
        road[1] += 'L';
    }
    road[1] += 'U';
 
    //次はずっと上からの右
    rep(i,Y){
        road[2] +='U';
    }
    rep(i,X) road[2] +='R';
 
    //最後は、戻る道順上1左X+1 下Y+1 右1
    road[3] += 'U';
    rep(i,X+1) road[3] += 'L';
    rep(i,Y+1) road[3] += 'U';
    road[3] +='R';

これの何がいけないって、

上はUP の Uだな。

下はUNDER の U だなって思って U と R を追加してました…

これだと上も下もUであらわされてるから間違いってことです。

さて

解法

まず、4つの道順がどうなるかを考える。

① スタート地点をS(S.x,S.y),ゴール地点をG(T.x,T.y)とする

②通る道だけ考えるんだったら、SからGに行く4通りの道を求めればいい。

③このように考えて、同じ座標を踏んではいけないという制約から、一歩目は 右か左か上か、下に行く。の四通りしかないことが分かる。

  • 一歩目が右の場合
    • まずT.xまで右に進む
    • その後、T.yまで上に進む
  • 一歩目が上の場合
    • まずT.yまで上に進む
    • その後、T.xまで右に進む

この二つが、SからGに行く最短のルートである。

  • 一歩目が左の場合
    • まず一歩左に行く
    • その後、T.y+1 まで上に行く
    • その後 T.xまで右に行く
    • 最後に一歩下に進む
  • 一歩目が下の場合
    • まず一歩下に行く
    • その後T.x+1まで右に行く
    • その後、T.yまで上に行く
    • 最後に一歩左

（座標表記と、何歩という表記が混ざっていてわかりずらくなってます。すみません。

(一歩目が左の場合の,その後T.xまで右に行くとか、一歩目が下の場合のT.yまで上に行くっていうのは、

最初に左、もしくは下に動いてしまっているため,

T.xまたはT.yまで行くにはT.x-S.x +１歩 または T.y - S.y +1 歩、右、もしくは上に移動するということに注意してください)

このように4つの道について考えることが出来れば、あとはそのうちの二つをGからSに行くものとして上下左右を反転して文字列を作ればいい。

僕の場合は、road[4]で、4つの経路を求めることにして

road[0]がSからGに行く、この時Sからの一歩目が右

road[1]がGからSに行く、Gからの一歩目は右

road[2]がSからGに行く、Sからの一歩目は上

road[3]がGからSに行く、Gからの一歩目は上

というように、SからGへ行くときは距離最短、GからSへ戻るときは少し遠回りをしないといけない。という風にしました。

一応画像も貼っておくので良かったら見てね f:id:niboshi_bisyoujo:20191123204704j:plain