สมมุติว่ามีกบกำลังข้ามแม่น้ำ แม่น้ำแบ่งออกเป็น x หน่วย และแต่ละหน่วยอาจมีหิน กบกระโดดบนหินได้ แต่ไม่สามารถกระโดดน้ำได้ เรามีรายชื่อตำแหน่งของหินที่เรียงจากน้อยไปมาก เราต้องตรวจสอบว่ากบสามารถข้ามแม่น้ำโดยการลงจอดบนหินก้อนสุดท้ายได้หรือไม่ ในขั้นต้น กบอยู่บนก้อนหินก้อนแรก และถือว่าการกระโดดครั้งแรกต้องมี 1 หน่วย
เมื่อกบกระโดดในปัจจุบันคือ k หน่วย การกระโดดครั้งต่อไปต้องเป็น k - 1, k หรือ k + 1 หน่วย และกบสามารถกระโดดไปข้างหน้าได้เท่านั้น
ดังนั้นหากอาร์เรย์ที่กำหนดเป็น [0,1,3,4,5,7,9,10,12] คำตอบจะเป็นจริงเช่น กบสามารถกระโดดไปที่หินก้อนที่ 1 ถึงก้อนที่ 2 และ 2 หน่วยไปที่ หินที่ 3 จากนั้นอีก 2 หน่วยไปยังหินที่ 4 จากนั้น 3 หน่วยถึงหินที่ 6, 4 หน่วยถึงหินที่ 7 และสุดท้าย 5 หน่วยถึงหินที่ 8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดแผนที่เรียกว่าเยี่ยมชมแล้ว
- กำหนดฟังก์ชัน canCross() ซึ่งจะใช้อาร์เรย์สโตน pos เริ่มต้นด้วย 0, k เริ่มต้นด้วย 0,
- คีย์ :=pos OR (กะซ้าย k 11 บิต)
- ถ้ามีคีย์อยู่ในการเยี่ยมชมแล้ว −
- กลับมาเยี่ยมชม[คีย์]
- สำหรับการเริ่มต้น i :=pos + 1 เมื่อฉัน <ขนาดของก้อนหิน อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- ช่องว่าง:=หิน[i] - หิน[pos]
- ถ้าช่องว่าง
- ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
- ถ้าช่องว่าง> k + 1 แล้ว −
- เข้าชมแล้ว[คีย์] :=false
- คืนค่าเท็จ
- ถ้าเรียกใช้ฟังก์ชัน canCross(stones, i, gap) ไม่ใช่ศูนย์ ดังนั้น −
- เข้าชมแล้ว[คีย์] =จริง
- คืนค่าจริง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
unordered_map < lli, int > visited;
bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
lli key = pos | k << 11;
if(visited.find(key) != visited.end())return visited[key];
for(int i = pos + 1; i < stones.size(); i++){
int gap = stones[i] - stones[pos];
if(gap < k - 1)continue;
if(gap > k + 1){
return visited[key] = false;
}
if(canCross(stones, i, gap))return visited[key] = true;
}
return visited[key] = (pos == stones.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {0,1,3,5,6,8,12,17};
cout << (ob.canCross(v));
} อินพุต
0,1,3,5,6,8,12,17
ผลลัพธ์
1
