C++で指定されたパスを生成するための最小停止点数を求める

本記事では、二次元平面上の移動経路から、その経路を実現するために最低限必要な停止点（ストップ）の数を求めるアルゴリズムを、C++のコード例とともに解説します。

問題の定義

• 二次元空間上に多数の点が存在し、それらを特定の順序で訪問する必要があります。
• ある点から別の点への移動は常に最短経路が選ばれ、経路の各区間は必ずグリッド線（水平線・垂直線）に沿って進みます。
• 点を訪問するために選ばれた経路が文字列として与えられます。このとき、与えられた経路を生成するために必要な最小の停止点数を求めます。

アルゴリズム

1. 各停止点を訪問する際の移動パターンを観察することで、この問題を解決できる
2. ある点から別の点へ最短経路で移動する場合、進む方向は1つ、多くても2つまでに限られる

つまり、ある区間内で「L（左）とR（右）」のように互いに逆方向への移動が現れた場合、そこには必ず中継点（停止点）が存在しなければならないということです。同様に「U（上）とD（下）」の組み合わせでも同じことが言えます。したがって、逆方向のペアが出現するたびに停止点を1つ追加していくことで、最小停止点数を求めることができます。

実装例

#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
    int n = path.length();
    map<char, int> directionMap;
    int stops = 1;
    for (int i = 0; i < n; ++i) {
        char direction = path[i];
        directionMap[direction] = 1;
        if ((directionMap['L'] && directionMap['R']) ||
        (directionMap['U'] && directionMap['D'])) {
            directionMap.clear();
            ++stops;
            directionMap[direction] = 1;
        }
    }
    return stops + 1;
}
int main() {
    string path = "LLUUULLDD";
    cout << "Minimum stops = " << getMinStops(path) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum stops = 3

コードの解説

getMinStops 関数では、map を使って現在の区間で使用された移動方向を記録しています。経路文字列を先頭から順に走査し、「LとR」または「UとD」という逆方向の組み合わせが検出された時点で、マップをクリアして停止点を1つ増やし、現在の方向から新たな区間として記録を開始します。

入力例 "LLUUULLDD" の場合、最初の LLUU の区間までは左と上のみの移動なので1つの区間で済みますが、続く L と後の R 相当の動きにより区間が分割され、結果として最小3つの停止点が必要となります。