C++で解く！2D平面上の点aから点bへの重複なし往復移動経路を求めるアルゴリズム

問題の概要

2次元平面上に2つの点 a と b があり、それぞれ座標 (x1, y1)、(x2, y2) を持っているとします。現在位置は点 a で、1回の移動ごとに上下左右のいずれかの方向へちょうど距離1だけ進むことができます。ここで、点 a から点 b へ移動し、その後点 a に戻り、さらに再度点 b へ向かうという一連の移動を行います。ただし、点 a と点 b 以外の同じ座標点を2回以上通ることは禁止されています。この旅全体で行う移動手順を求めて出力してください。移動方向は、右なら「R」、左なら「L」、上なら「U」、下なら「D」の文字で表します。なお、x2 > x1 かつ y2 > y1 が常に成り立つものとします。

例として、入力が x1 = 0、y1 = 1、x2 = 3、y2 = 4 の場合、出力は UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU になります。

解法のアプローチ

この問題は、a と b を対角とする長方形を少しずつずらしながら3周描くことで解けます。具体的には、以下の手順に従います。

s := 空文字列
i を 0 から y2 - y1 未満まで 1 ずつ増やしながら:
    s の末尾に "U" を追加
i を 0 から x2 - x1 未満まで 1 ずつ増やしながら:
    s の末尾に "R" を追加
i を 0 から y2 - y1 未満まで 1 ずつ増やしながら:
    s の末尾に "D" を追加
i を 0 から x2 - x1 未満まで 1 ずつ増やしながら:
    s の末尾に "L" を追加
s の末尾に "LU" を追加
i を 0 から y2 - y1 未満まで 1 ずつ増やしながら:
    s の末尾に "U" を追加
i を 0 から x2 - x1 未満まで 1 ずつ増やしながら:
    s の末尾に "R" を追加
s の末尾に "RD" を追加
s の末尾に "RD" を追加
i を 0 から y2 - y1 未満まで 1 ずつ増やしながら:
    s の末尾に "D" を追加
i を 0 から x2 - x1 未満まで 1 ずつ増やしながら:
    s の末尾に "L" を追加
s の末尾に "LU" を追加
s を返す

なぜこの手順で成立するのか

最初の「U・R・D・L」の一連の移動で、a と b を対角とする外側の長方形を一周し、点 a に戻ります。続く「LU」で左上へ1マス斜めにずれることで、前周とは異なるマスから2周目を開始できます。さらに2周目の後の「RD」「RD」で位置を調整して3周目へ移行するため、途中の点を一切重複させることなく、a → b → a → b という往復移動を実現できます。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

string solve(int x1, int y1, int x2, int y2){
    string s = "";
    for(int i = 0; i < y2 - y1; i++)
        s.append("U");
    for(int i = 0; i < x2 - x1; i++)
        s.append("R");
    for(int i = 0; i < y2 - y1; i++)
        s.append("D");
    for(int i = 0; i < x2 - x1; i++)
        s.append("L");
    s.append("LU");
    for(int i = 0; i < y2 - y1; i++)
        s.append("U");
    for(int i = 0; i < x2 - x1; i++)
        s.append("R");
    s.append("RD");
    s.append("RD");
    for(int i = 0; i < y2 - y1; i++)
        s.append("D");
    for(int i = 0; i < x2 - x1; i++)
        s.append("L");
    s.append("LU");
    return s;
}
int main() {
    int x1 = 0, y1 = 1, x2 = 3, y2 = 4;
    cout << solve(x1, y1, x2, y2);
    return 0;
}

入力

0, 1, 3, 4

出力

UUURRRDDDLLLLUUUURRRRDRDDDDLLLLU