Người Gửi: ABC
- Problem:
Một robot chỉ có thể di chuyển sang phải hoặc sang trái. Dãy di chuyển của nó được kí hiệu là một chuỗi, nhưng do sơ suất của người ghi chép, nên một số bước đi không ghi lại được. Nhiệm vụ của bạn là xác định xem robot có thể đi cách xa nhất vị trí ban đầu là ban nhiêu?
Input
Một dòng duy nhất chứa chuỗi di chuyển, mỗi kí tự có thể là:
- ‘L’ nếu di chuyển sang trái
- ‘R’ nếu di chuyển sang phải
- ‘ ?’ nếu không xác định.
Output
Khoảng cách xa nhất đến vị trí ban đầu.
Example:
Input
LLLRLRRR
Output:
3
Input
R???L
Output:
4
- Solution:
Input
R???L
Output:
4
Ở bài này với mỗi bước di chuyển ? bạn xác định xem hướng nào là tối đa nhất; Lm, Rm là trái phải tối đa mà nó dịch tại thời điể đó.
Đây là code tham khảo của thầy P.Xuân Tích:
- Code:
#include <iostream>
#include <string>
using namespace std;
int main ()
{
string step;
cin>>step;
int stepMax=0;
int L=0, R=0;
int Lm=0, Rm=0;
for (int i=0; i<step.length(); i++)
{
if (step[i]=='L')
{
L++;
Lm++;
if (Lm-R>stepMax) stepMax=Lm-R;
}
else if (step[i]=='R')
{
R++;
Rm++;
if (Rm-L>stepMax) stepMax=Rm-L;
}
else
{
Lm++;
if (Lm-R>stepMax) stepMax=Lm-R;
Rm++;
if (Rm-L>stepMax) stepMax=Rm-L;
}
}
cout<<stepMax;
return 0;
}