C++で文字列内のセルに複数回アクセスできるかどうかを判定する方法

問題の概要

ドット（.）と数字から構成される文字列を考えます。ドットはそのセルが空であることを示し、あるセルに数字 x が入っている場合は、そのセルから文字列内を左右どちらかの方向へ x 歩移動できることを意味します。このとき、同じセルを複数回訪問できるかどうかを判定するのが本記事の課題です。

例として、文字列が「.2...2..」である場合を考えてみましょう。この場合、4番目のセルには2通りの経路で到達できます。ひとつは2番目のセルから右へ2歩進む方法、もうひとつは6番目のセルから左へ2歩進む方法です。

アルゴリズムの考え方

この問題を解くために、各セルの訪問回数を記録する配列 visited[] を用意します。処理の手順は以下の通りです。

まず文字列を先頭から走査し、現在の文字を確認します。文字がドットであれば何も行いません。数字 x であった場合は、範囲 [i − x, i + x] 内にあるすべてのセルについて、visited 配列のカウントを1ずつ増やします。走査が完了したら、visited 配列を再度確認し、カウントが2以上になっているセルが存在するかどうかを調べます。存在すれば「複数回訪問可能」、存在しなければ「不可能」と判定できます。

C++による実装例

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 同じセルを複数回訪問できるかどうかを判定する関数
bool canVisitCellMoreThanOnce(const string& s) {
   int n = s.length();
   vector<int> visited(n, 0); // 各セルの訪問回数を記録

   // 文字列を走査
   for (int i = 0; i < n; i++) {
       if (s[i] == '.') {
           continue; // ドットの場合は何もしない
       }
       int x = s[i] - '0'; // 移動できる歩数
       // 範囲 [i - x, i + x] 内のセルの訪問回数を増やす
       for (int j = max(0, i - x); j <= min(n - 1, i + x); j++) {
           visited[j]++;
       }
   }

   // 複数回訪問されたセルが存在するかチェック
   for (int i = 0; i < n; i++) {
       if (visited[i] > 1) {
           return true;
       }
   }
   return false;
}

int main() {
   string s = ".2...2..";
   if (canVisitCellMoreThanOnce(s))
       cout << "複数回訪問できるセルが存在します" << endl;
   else
       cout << "複数回訪問できるセルは存在しません" << endl;
   return 0;
}

出力結果

複数回訪問できるセルが存在します

動作の解説

上記の例では、インデックス1の「2」が範囲 [0, 3] のセルをカバーし、インデックス5の「2」が範囲 [3, 7] のセルをカバーします。その結果、インデックス3（4番目のセル）の訪問回数が2となり、複数回の訪問が可能であることが確認できます。

計算量

時間計算量は O(n × k) となります。ここで n は文字列の長さ、k は出現する数字の最大値です。数字が1桁（0〜9）に限定される場合、実質的に O(n) で処理できます。空間計算量は訪問回数を格納する配列が必要なため O(n) です。