Giả sử chúng ta có một mảng các số nguyên không âm arr, ban đầu chúng ta được định vị ở chỉ số bắt đầu của mảng. Khi chúng ta có mặt ở chỉ mục i, chúng ta có thể nhảy đến i + arr [i] hoặc i - arr [i], kiểm tra xem chúng ta có thể đạt đến bất kỳ chỉ mục nào có giá trị 0. Chúng ta phải lưu ý rằng chúng ta không thể nhảy ra ngoài mảng bất kỳ lúc nào. Vì vậy, nếu đầu vào là:arr =[4,2,3,0,3,1,2] và bắt đầu từ 5, thì đầu ra sẽ là true, như di chuyển 5 → 4 → 1 → 3 hoặc 5 → 6 → 4 → 1 → 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của arr
- xác định hàng đợi q, chèn bắt đầu vào q, xác định một tập hợp được gọi là đã truy cập và chèn bắt đầu vào tập hợp đã truy cập
- trong khi hàng đợi không trống,
- curr:=phần tử phía trước của q, xóa phần tử phía trước khỏi q
- nếu mảng [curr] bằng 0, thì trả về true
- nếu curr + arr [curr]
- chèn curr + arr [curr] vào q
- chèn curr + arr [curr] vào đã truy cập
- nếu curr - arr [curr]> =0 và curr - arr [curr] không có trong nhóm đã truy cập thì
- chèn curr - arr [curr] vào q
- chèn curr - arr [curr] vào đã truy cập
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
queue <int> q;
q.push(start);
set <int> visited;
visited.insert(start);
while(!q.empty()){
int curr = q.front();
q.pop();
if(arr[curr] == 0)return true;
if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
q.push(curr + arr[curr]);
visited.insert(curr + arr[curr]);
}
if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
q.push(curr - arr[curr]);
visited.insert(curr - arr[curr]);
}
}
return false;
}
};
main(){
vector<int> v = {4,2,3,0,3,1,2};
Solution ob;
cout << (ob.canReach(v, 5));
} Đầu vào
[4,2,3,0,3,1,2] 5
Đầu ra
1