ความเป็นไปได้ของการออกจากเขาวงกตใน C++

ในปัญหานี้ เราได้รับเขาวงกตของ n จำนวนเต็ม แต่ละจำนวนเต็มระบุจำนวนการเคลื่อนที่ที่ต้องทำ พร้อมกับทิศทางที่ระบุโดยใช้ '>' และ '<' งานของเราคือค้นหาว่าสามารถเคลื่อนที่ออกจากเขาวงกตได้หรือไม่ หากจุดเริ่มต้นคือตำแหน่งที่ดัชนี 0

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input -

3 2 1 1 4
> < > > 

Output - YES

Explanation - เคลื่อนที่จากจุดเริ่มต้น เราจะเคลื่อนที่ 2 ตำแหน่งไปข้างหน้า แล้ว 1 ตำแหน่งไปข้างหน้า แล้ว 4 ตำแหน่งไปข้างหน้า สิ่งนี้จะเคลื่อนที่ออกจากเขาวงกต

เพื่อแก้ปัญหานี้ เราจะตรวจสอบว่าการเคลื่อนที่ออกจากเขาวงกตเป็นไปได้หรือไม่ สำหรับสิ่งนี้ เราต้องไปต่ำกว่า 0 หรือสูงกว่า n เริ่มจาก 0 เราจะประมวลผลทิศทางตามเครื่องหมายโดยจำนวนเต็มที่กำหนด และตรวจสอบว่าถึงจุดสิ้นสุดหรือไม่

เงื่อนไขอีกอย่างที่อาจเกิดขึ้นคือ infinite loop คือเงื่อนไขที่ผู้ใช้ไม่เคยหลุดออกจากเขาวงกต นี่คือเมื่อเรากลับมาที่ตำแหน่งที่เคยเยี่ยมชมแล้ว ดังนั้นเพื่อตรวจสอบเงื่อนไขนี้ เราจะทำเครื่องหมายตำแหน่งที่เยี่ยมชมทั้งหมด

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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