在这个问题中,我们给出了一个由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); }
输出结果
它会从迷宫中出来