ความเป็นไปได้ของการย้ายออกจากเขาวงกตใน 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 << "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