C++で解くリスのナッツ収集シミュレーション ― 最小移動距離を求めるアルゴリズム

問題概要

1本の木、1匹のリス、そして複数のナッツがフィールド上にあります。それぞれの位置は2次元グリッドのセルで表現されます。この問題の目的は、リスがすべてのナッツを集めて木の下に1個ずつ運ぶときの最小移動距離を求めることです。

リスの行動には次の制約があります。

• 一度に持てるナッツは最大1個
• 移動は上下左右の4方向で、隣接するセルへのみ可能
• 距離は移動回数(ステップ数)で表される

たとえば、入力が「高さ: 5 / 幅: 7 / 木の位置: [2,2] / リスの位置: [4,4] / ナッツ: [[3,0], [2,5]]」の場合、出力は 12 となります。

解法のポイント

まず、2点間の距離をマンハッタン距離で計算する補助関数 calc() を用意します。これは |x1 − x2| + |y1 − y2| を返します。

基本的な発想はシンプルです。もしリスが常に木を拠点として動くなら、各ナッツを「取りに行って戻ってくる」往復で運ぶことになり、総距離は「木〜ナッツ間の距離 × 2」の合計になります。ところが実際には、リスは最初の1個目だけ、木ではなく自分の初期位置から直接ナッツを拾いに行けます。ここでどれだけ距離を節約できるかが鍵になります。

そこで、各ナッツについて「木を経由する場合と比べてどれだけ節約できるか」を計算し、その最大値 maxDiff を求めます。最終的な答えは、全ナッツの往復距離の合計から maxDiff を差し引いた値です。

アルゴリズムの手順

1. calc(x1, y1, x2, y2) を定義し、|x1 − x2| + |y1 − y2| を返します。
2. minDistance(height, width, tree, sq, nuts) を定義します。
3. ret := 0、maxDiff := −∞ で初期化します。
4. i = 0 からナッツの個数だけ繰り返します。
   • dist := calc(tree[0], tree[1], nuts[i][0], nuts[i][1])
   • ret := ret + 2 × dist
   • maxDiff := max(maxDiff, 2 × dist − (dist + calc(nuts[i][0], nuts[i][1], sq[0], sq[1])))
5. ret − maxDiff を返します。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int calc(int x1, int y1, int x2, int y2){
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int minDistance(int height, int width, vector<int>& tree, vector<int>& sq, vector<vector<int>>& nuts) {
        int ret = 0;
        int maxDiff = INT_MIN;
        for (int i = 0; i < nuts.size(); i++) {
            int dist = calc(tree[0], tree[1], nuts[i][0], nuts[i][1]);
            ret += 2 * dist;
            maxDiff = max(maxDiff, 2 * dist - (dist + calc(nuts[i][0], nuts[i][1], sq[0], sq[1])));
        }
        return ret - maxDiff;
    }
};
int main(){
    Solution ob;
    vector<int> v = {2,2}, v1 = {4,4};
    vector<vector<int>> v2 = {{3,0}, {2,5}};
    cout << (ob.minDistance(5,7,v, v1, v2));
}

入力

5, 7, {2,2},{4,4}, {{3,0}, {2,5}}

出力

12

動作の検証

この入力例では、木(2,2)からナッツ(3,0)までの距離は 3、ナッツ(2,5)までの距離も 3 です。すべてのナッツを木から往復で運ぶと 2×3 + 2×3 = 12 となります。リス(4,4)から直接ナッツ(2,5)へ向かう距離は 3 で、木を経由する場合と変わらないため節約額は 0(maxDiff = 0)。一方、ナッツ(3,0)へ直接向かうと距離は 5 になり、かえって遠回りになってしまいます。したがって答えは 12 − 0 = 12 です。