C++で全ての点を訪問するための最小時間を求めるアルゴリズム

配列として与えられた複数の点(座標)があります。このとき、すべての点を訪問するのに必要な最小時間(秒)を求める問題を考えます。ただし、以下の条件が課せられています。

• 1秒につき、上下・左右・斜めのいずれかの方向へ1マス移動できる
• 点は配列に現れる順序どおりに訪問しなければならない

例えば、点が [(1, 1), (3, 4), (-1, 0)] と与えられた場合、出力は 7 になります。最短経路をたどる際の移動の順序は、(1, 1) → (2, 2) → (3, 3) → (3, 4) → (2, 3) → (1, 2) → (0, 1) → (-1, 0) となります。

解き方のアプローチ

この問題を解く鍵となるのは、チェビシェフ距離(Chebyshev distance) の考え方です。斜め移動が許されているため、隣接する2点間を移動するのに必要な秒数は、「X座標の差の絶対値」と「Y座標の差の絶対値」のうち大きい方と一致します。これは、斜めに移動すればX方向とY方向を同時に進めるためです。

したがって、連続する2点ごとにX座標の差とY座標の差を計算し、その最大値を順番に加算していくだけで答えが求まります。計算量は O(n) と非常に効率的です。

実装例

以下はC++による実装例です。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& p) {
        int ans = 0;
        int n = p.size();
        for(int i = 1; i < n; i++){
            ans += max(abs(p[i][0] - p[i-1][0]), abs(p[i][1] - p[i-1][1]));
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> c = {{1,1},{3,4},{-1,0}};
    cout << ob.minTimeToVisitAllPoints(c);
}

入力

[[1,1],[3,4],[-1,0]]

出力

7

このように、各2点間の移動コストを max(|dx|, |dy|) で求めて合計するだけで、斜め移動を活用した最短時間を簡単に計算できます。