Khả năng thoát khỏi mê cung (Maze) trong C++

Trong bài toán này, cho mê cung n số nguyên, mỗi số chỉ số bước di chuyển. Cùng với hướng dùng '>' và '<'. Nhiệm vụ tìm có thể thoát khỏi mê cung hay không nếu điểm bắt đầu là vị trí chỉ số 0.

Ví dụ minh họa:

Đầu vào -

3 2 1 1 4 
> < > >

Kết quả - YES

Giải thích - Từ đầu, đi 2 vị trí tới, rồi 1 vị trí tới, rồi 4 vị trí tới. Sẽ thoát khỏi mê cung.

Để giải bài toán, kiểm tra có thể thoát ra không. Cần đi dưới 0 hoặc trên n. Bắt đầu từ 0, xử lý hướng theo dấu bằng số bước cho trước. Kiểm tra xem có đến cuối không.

Một điều kiện khác: vòng lặp vô tận - không bao giờ thoát ra, khi quay lại vị trí đã thăm. Để kiểm tra, đánh dấu tất cả vị trí đã thăm.

Chương trình minh họa

#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 << "Ở trong mê cung mãi mãi"; 
    else 
        cout << "Sẽ thoát ra khỏi mê cung"; 
} 

int main() { 
    int n = 3; 
    string s = ">><"; 
    int a[] = { 1, 2, 4 }; 
    isMazeSolvable(a, n, s); 
}

Kết quả

Sẽ thoát ra khỏi mê cung