Find if bike racer A defends bike racer B in race when he can jump on his path on seeing a ‘.’ and if he sees an obstacle ‘@’ in his path he cannot path through it.
Note : Race direction is decided by direction of A-B
Examples :
Input : 5 2 @A@B@ Output : A can reach B Input : 6 1 B....A Output : A can reach B Input : 7 3 B..@..A Output : It is not possible for A to reach B Input : 6 2 ..AB.. Output : It is not possible for A to reach B
Approach:
This can be solve using following algorithm
1. find the first ocuurance of A and B in string and calculate the absoulute
difference between them
2. if diff%k !=0 means we can not reach B in the given jumps
3. mainatain a check flag and initialise it with true initially
4. run a loop from the minimum index among A and B till the maximum index among
between A and B , update the loop with the given number of jumps (k) and do the
following
a) if any where the '@' occurs , set check as false means we can not move as it is
an obstacle , given in the problem above
5. check the value of check_ varible if it is true
means we can reach , print message A can reach B
if it is false print message
A can not reach B
Below is the implementation code:
//C++ program to find if A defend B in bike race
#include<bits/stdc++.h>
using namespace std;
//Driver function
int main(){
int n = 6;
//cin>>n;
int k = 1;
//cin>>k;
string s = "B....A";
// cin>>s;
// find the first indexes of A and B
int index1 = s.find_first_of('A');
int index2 = s.find_first_of('B');
// find aabsoulute difference
int diff = abs(index1 - index2);
bool check = true;
// if(diff == 0){
// check = true;
// }
if(diff%k != 0){ // we can not reach
check = false;
}
for(int i=min(index1, index2); i<max(index1, index2); i+=k){
if(s[i] == '@'){
check = false; // it is an obstacle , we can not move
}
}
if(check){ // true
cout<<"A can reach B";
}else{ // false
cout<<"It is not possible for A to reach B";
}
return 0;
}
Output :
A can reach B