C++で迷路から抜け出す可能性

この問題では、n個の整数の迷路が与えられます。各整数は、実行する移動の数を示します。 「>」と「<」を使用して示された方向とともに。私たちの仕事は、開始点が0インデックスの位置である場合に、迷路の外に移動できるかどうかを確認することです。

問題を理解するために例を見てみましょう

入力 −

3
2 1 1 4
> < > >

出力 −はい

説明 −最初から移動して、2ポジション先に移動し、次に1ポジション先に移動し、次に4ポジション先に移動します。これで迷路が動きます。

この問題を解決するために、迷路から抜け出すことができるかどうかを確認します。このためには、0より下またはnより上に移動する必要があります。 0から始めて、与えられた整数の場所による符号に基づいて方向を処理します。そして、終わりに達したかどうかを確認します。

発生する可能性のあるもう1つの条件は、無限ループです。つまり、ユーザーが迷路から抜け出さない条件です。これは、訪問位置に戻ったときです。したがって、この状態を確認するために、訪問したすべての場所にマークを付けます。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
void isMazeSolvable (int a[], int n, string s){
   int mark[n] = {0};
   int start = 0;
   int possible = 1;
   while (start >= 0 && start < n){
      if (s == "<"){
         if (mark[start] == 0){
            mark[start] = 1;
            start -= a[start];
         } else {
            possible = 0;
            break;
         }
      } else {
         if (mark[start] == 0){
            mark[start] = 1;
            start += a[start];
         } else {
            possible = 0;
            break;
         }
      }
   }
   if (possible == 0)
      cout << "It stays inside the maze forever";
   else
      cout << "It will come out of the maze";
}
int main (){
   int n = 3;
   string s = ">><";
   int a[] = { 1, 2, 4 };
   isMazeSolvable (a, n, s);
}

出力

It will come out of the maze