Trong bài toán này, chúng ta được cung cấp một mê cung gồm n số nguyên, mỗi số nguyên cho biết số bước di chuyển cần thực hiện. Cùng với hướng được chỉ định bằng cách sử dụng ‘>’ và ‘<’. Nhiệm vụ của chúng ta là tìm xem liệu có thể di chuyển ra khỏi mê cung hay không nếu điểm xuất phát là vị trí 0 chỉ mục.
Hãy lấy một ví dụ để hiểu vấn đề
Đầu vào -
3 2 1 1 4 > < > >
Đầu ra - CÓ
Giải thích - di chuyển từ đầu, chúng ta sẽ di chuyển 2 vị trí phía trước, sau đó 1 vị trí phía trước, sau đó 4 vị trí phía trước. Điều này sẽ di chuyển mê cung của chúng ta.
Để giải quyết vấn đề này, chúng tôi sẽ kiểm tra xem việc di chuyển ra khỏi mê cung có khả thi hay không. Đối với điều này, chúng ta cần phải đi xuống dưới 0 hoặc trên n. Bắt đầu từ 0, chúng tôi sẽ xử lý hướng dựa trên dấu hiệu bằng các vị trí số nguyên đã cho. Và kiểm tra xem kết thúc đã đạt được chưa.
Một điều kiện nữa có thể phát sinh là vòng lặp vô hạn, tức là điều kiện khi người dùng không bao giờ thoát ra khỏi mê cung, đây là khi chúng ta quay trở lại vị trí truy cập. Vì vậy, để kiểm tra điều kiện này, chúng tôi sẽ đánh dấu tất cả các địa điểm đã ghé thăm.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi
#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);
} Đầu ra
It will come out of the maze