在C++中计算走出迷宫的可能性

在这个问题中，我们给出了一个由n个整数组成的迷宫，每个整数表示要做的步数。以及用“>”和“<”指示的方向。我们的任务是找出是否有可能走出迷宫，如果起点是0索引的位置。

让我们以一个例子来了解问题

输入-

3
2 1 1 4
> < > >

输出-是

说明-从一开始，我们将向前移动2个位置，然后向前移动1个位置，然后向前移动4个位置。这会让我们走出迷宫。

为了解决这个问题，我们将检查是否可以移出迷宫。为此，我们需要低于0或高于n。从0开始，我们将根据符号以给定的整数位置处理方向。并检查是否达到终点。

可能出现的另一种情况是无限循环，即用户从不走出迷宫时的状态，即我们回到探访位置时的状态。因此，要检查这种情况，我们会标记所有访问过的地方。

示例

显示我们解决方案实施情况的程序

#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 << "它永远留在迷宫里";
   else
      cout << "它会从迷宫中出来";
}
int main (){
   int n = 3;
   string s = ">><";
   int a[] = { 1, 2, 4 };
   isMazeSolvable (a, n, s);
}

输出结果

它会从迷宫中出来