C++でバッタがターゲットに到達できるかどうかを判定する方法

長さ n の文字列 S と整数 k が与えられる問題を考えてみましょう。文字列には4種類の文字が含まれており、それぞれ複数のセル(マス)を表しています。バッタはジャンプを繰り返してターゲットに到達しようとしています。

各文字の意味は以下の通りです。

• '.': 対応するセルが空であることを表します
• '#': 対応するセルに障害物があり、バッタはそこへジャンプできません
• 'G': バッタの開始位置を表します
• 'T': 目標となるターゲットのセルを表します

バッタは現在位置からちょうど k セル先にしかジャンプできません。このとき、バッタがターゲットに到達できるかどうかを判定する必要があります。

例えば、入力が S = "#G#T#"、k = 2 の場合、出力は True になります。これは、G から T までの距離が2セルであり、k も2なので、バッタは1回のジャンプでターゲットに到達できるためです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• n を文字列 S のサイズとします
• x を S 内の 'G' の位置、y を 'T' の位置とします
• x > y の場合は、x と y を入れ替えます
• i を x で初期化し、i < y の間、i を i + k ずつ更新しながらループします
  • 途中で S[i] が '#' と一致した場合は、ループを抜けます
• ループ終了時に i == y であれば true を返し、そうでなければ false を返します

このアルゴリズムのポイントは、バッタが必ず k セルずつジャンプするため、開始位置から k 刻みで進んだ位置だけを確認すればよいという点です。障害物にぶつかることなく、ちょうどターゲットの位置に着地できれば到達可能と判断できます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(string S, int k)
{
    int n = S.size();
    int i;
    int x = S.find('G');
    int y = S.find('T');
    if (x > y)
        swap(x, y);
    for (i = x; i < y; i += k)
    {
        if (S[i] == '#')
            break;
    }
    if (i == y)
        return true;
    else
        return false;
}
int main()
{
    string S = "#G#T#";
    int k = 2;
    cout << solve(S, k) << endl;
}

入力

"#G#T#", 2

出力

1

出力が 1(true)となっており、バッタが1回のジャンプでターゲットに到達できることが確認できます。このアルゴリズムの計算量は O(n/k) であり、文字列の長さに対して効率的に動作します。