이 문제에서 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 << "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