Mã C ++ để tìm bước nhảy tối thiểu để ếch về đến nhà

Giả sử chúng ta có một chuỗi nhị phân S với n bit và một số khác d. Trên một trục số, một con ếch muốn đến điểm n thì bắt đầu từ điểm 1. Con ếch có thể nhảy sang phải một khoảng cách không quá d. Đối với mỗi điểm từ 1 đến n nếu có một bông hoa lily, nó được đánh dấu là 1 và 0 nếu không có. Con ếch chỉ có thể nhảy ở những điểm có hoa loa kèn. Chúng ta phải tìm số lần nhảy tối thiểu mà con ếch cần để đạt được n. Nếu không thể, hãy trả về -1.

Vì vậy, nếu đầu vào giống như S ="10010101"; d =4, thì đầu ra sẽ là 2, vì từ vị trí 1, nó nhảy lên 4, sau đó ở chỉ số 8 (n).

Các bước

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

n := size of s
x := 0
y := 0
while (x < n - 1 and y <= n), do:
   if s[x] is same as '1', then:
      x := x + d
      increase y by 1
   Otherwise
      (decrease x by 1)
if y >= n, then:
   return -1
Otherwise
   return y

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d){
   int n = s.size();
   int x = 0, y = 0;
   while (x < n - 1 && y <= n){
      if (s[x] == '1')
         x += d, ++y;
      else
         --x;
   }
   if (y >= n)
      return -1;
   else
      return y;
}
int main(){
   string S = "10010101";
   int d = 4;
   cout << solve(S, d) << endl;
}

Đầu vào

"10010101", 4

Đầu ra

2