数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 迷宫逃脱可能性
在这个问题中，我们给定一个由 n 个整数构成的迷宫，每个整数表示需要移动的步数，以及用 ‘>’ 和 ‘<’ 表示的方向。我们的任务是判断从索引 0 位置出发，是否能够走出迷宫。
让我们通过一个例子来理解这个问题
输入 −
3 2 1 1 4 > < > >
输出 − YES
解释 − 从起点开始，我们将向前移动 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 << "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
更新于: 2020年4月17日
220 次浏览
广告