Mã C ++ để tìm chuỗi hướng giảm chuyển động của rô bốt

Giả sử chúng ta có một chuỗi S với n chữ cái. Các chữ cái là 'R' hoặc 'U'. Trên mặt phẳng 2D, rô bốt có thể đi sang phải hoặc đi lên. Khi nó là 'R' nó di chuyển sang phải và khi nó là 'U' nó di chuyển lên trên. Tuy nhiên chuỗi quá lớn, chúng tôi muốn làm cho chuỗi nhỏ hơn. Một cặp như "RU" hoặc "UR" sẽ được thay thế bằng cách di chuyển theo đường chéo "D". Chúng tôi phải tìm độ dài của chuỗi đã giảm được cập nhật cuối cùng.

Vì vậy, nếu đầu vào là S ="RUURU", thì đầu ra sẽ là 5, vì chuỗi sẽ là "DUD"

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 -

ans := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is not equal to S[i + 1], then:
      (increase i by 1)
   (increase ans by 1)
return ans

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 ans = 0;
   int n = S.size();
   for (int i = 0; i < n; ++i){
      if (S[i] != S[i + 1])
         i++;
      ans++;
   }
   return ans;
}
int main(){
   string S = "RUURU";
   cout << solve(S) << endl;
}

Đầu vào

"RUURU"

Đầu ra

3