Ếch nhảy trong C ++

Giả sử có một con ếch đang băng qua sông. Sông được chia thành x đơn vị và tại mỗi đơn vị có thể có một viên đá. Con ếch có thể nhảy trên đá, nhưng không phải nước. Ở đây chúng ta có một danh sách các vị trí của đá theo thứ tự tăng dần được sắp xếp, chúng ta phải kiểm tra xem con ếch có thể vượt sông bằng cách đáp xuống hòn đá cuối cùng hay không. Ban đầu, con ếch ở trên viên đá đầu tiên và giả sử bước nhảy đầu tiên phải bằng 1 đơn vị.

Khi bước nhảy hiện tại của con ếch là k đơn vị, thì bước nhảy tiếp theo của nó phải là k - 1, k hoặc k + 1 đơn vị. Và ếch chỉ có thể nhảy theo hướng về phía trước.

Vì vậy, nếu mảng đã cho giống như [0,1,3,4,5,7,9,10,12], thì câu trả lời sẽ là đúng, con ếch có thể nhảy từ viên đá 1 đến viên đá thứ 2, 2 đơn vị để Đá thứ 3, sau đó là 2 đơn vị đến viên đá thứ 4, sau đó 3 đơn vị đến viên đá thứ 6, 4 đơn vị đến viên đá thứ 7 và cuối cùng là 5 đơn vị đến viên đá thứ 8.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ được gọi là đã ghé thăm
• Định nghĩa một hàm canCross (), hàm này sẽ lấy một mảng đá, pos khởi tạo nó bằng 0, k khởi tạo nó bằng 0,
• key:=pos OR (dịch trái k 11 bit)
• nếu khoá có trong phần đã truy cập, thì -
  • quay lại đã ghé thăm [key]
• để khởi tạo i:=pos + 1, khi tôi
• khoảng trống:=stone [i] - stone [pos]
• if gap
• Bỏ qua phần sau, chuyển sang phần lặp tiếp theo

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

0,1,3,5,6,8,12,17

Đầu ra

1