สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มไม่เป็นลบ arr เราอยู่ในตำแหน่งเริ่มต้นที่ดัชนีเริ่มต้นของอาร์เรย์ เมื่อเราอยู่ที่ดัชนี i เราสามารถข้ามไปที่ i + arr[i] หรือ i - arr[i] ตรวจสอบว่าเราสามารถเข้าถึงดัชนีใด ๆ ที่มีค่า 0 ได้หรือไม่ เราต้องจำไว้ว่าเราไม่สามารถกระโดดออกจาก อาร์เรย์ได้ตลอดเวลา ดังนั้นหากอินพุตเป็นดังนี้:arr =[4,2,3,0,3,1,2] และเริ่มจาก 5 ผลลัพธ์จะเป็นจริงตามที่ย้าย 5 → 4 → 1 → 3 หรือ 5 → 6 → 4 → 1 → 3.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ arr
- กำหนดคิว q แทรก start ลงใน q กำหนดชุดที่เรียกว่า visit และแทรก start ลงในชุดที่เยี่ยมชม
- ในขณะที่คิวไม่ว่าง
- curr :=องค์ประกอบด้านหน้าของ q ลบองค์ประกอบด้านหน้าออกจาก q
- ถ้า array[curr] เป็น 0 ให้คืนค่า true
- ถ้า curr + arr[curr]
- ใส่ curr + arr[curr] ลงใน q
- ใส่ curr + arr[curr] เข้าไป
- ถ้า curr - arr[curr]>=0 และ curr - arr[curr] ไม่อยู่ในชุดที่เข้าชมแล้ว
- แทรก curr - arr[curr] ลงใน q
- ใส่ curr - arr[curr] เข้าไป
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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));
} อินพุต
[4,2,3,0,3,1,2] 5
ผลลัพธ์
1
