けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 051 C - Back and Forth (300 点)

ちょっとした構築系問題という感じかな...

問題へのリンク

問題概要

二次元平面上の二点  (s_x, s_y), (t_x, t_y) が与えられる。 s_x, s_y, t_x, t_y はすべて整数である。

今、 (s_x, s_y) から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら  (t_x, t_y) に行き、またそこから出発して  (s_x, s_y) に戻り、さらにまた  (t_x, t_y) に行って、 (s_x, s_y) に戻りたい。

ただし、往復する過程で「同じ座標」を二度通ってはいけない。最短時間で往復を実現する経路を 1 つ求めよ。

制約

  •  -1000 \le s_x \lt t_x \le 1000
  •  -1000 \le s_y \lt t_y \le 1000

考えたこと

下図みたいな動きをすれば OK。1 回目と 2 回目ともに

  • 青線で行って
  • 赤線で帰る (赤線ではほんの少しだけ寄り道をする)

ここで、 (s_x, s_y) (t_x, t_y) との位置関係が気になるが、問題文によると常に  (t_x, t_y) (s_x, s_y) の右上にあるので大丈夫。

f:id:drken1215:20190522214352p:plain

#include <iostream>
#include <string>
using namespace std;

int main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    int dx = tx - sx, dy = ty - sy;
    
    string res = "";

    // 1 回目
    for (int i = 0; i < dx; ++i) res += "R";
    for (int i = 0; i < dy; ++i) res += "U";
    for (int i = 0; i < dx; ++i) res += "L";
    for (int i = 0; i < dy; ++i) res += "D";

    // 2 回目
    res += "D";
    for (int i = 0; i <= dx; ++i) res += "R";
    for (int i = 0; i <= dy; ++i) res += "U";
    res += "L";
    res += "U";
    for (int i = 0; i <= dx; ++i) res += "L";
    for (int i = 0; i <= dy; ++i) res += "D";
    res += "R";
    cout << res << endl;
}