Kapil Friend's OA question
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
#include <bits/stdc++.h>
using namespace std;
void helper(vector<vector<char>> grid, int si, int sj,vector<vector<int>> visited,char par, int turns,bool &ans){
if(si < 0 || sj < 0 || si >= grid.size() || sj >= grid[0].size() || visited[si][sj] || grid[si][sj] == 'x'){
return;
}
if(grid[si][sj] == 'W'){
if(turns >=0){
// cout<<si<<" "<<sj<<" "<<turns<<endl;
ans = true;
}
return;
}
visited[si][sj] = true;
if(par == 'L'){
helper(grid,si+1,sj,visited,'D',turns-1,ans);
helper(grid,si-1,sj,visited,'U',turns-1,ans);
helper(grid,si,sj+1,visited,'R',turns-1,ans);
helper(grid,si,sj-1,visited,'L',turns,ans);
}else if(par == 'R'){
helper(grid,si+1,sj,visited,'D',turns-1,ans);
helper(grid,si-1,sj,visited,'U',turns-1,ans);
helper(grid,si,sj+1,visited,'R',turns,ans);
helper(grid,si,sj-1,visited,'L',turns-1,ans);
}else if(par == 'D'){
helper(grid,si+1,sj,visited,'D',turns,ans);
helper(grid,si-1,sj,visited,'U',turns-1,ans);
helper(grid,si,sj+1,visited,'R',turns-1,ans);
helper(grid,si,sj-1,visited,'L',turns-1,ans);
}else if(par == 'U'){
helper(grid,si+1,sj,visited,'D',turns-1,ans);
helper(grid,si-1,sj,visited,'U',turns,ans);
helper(grid,si,sj+1,visited,'R',turns-1,ans);
helper(grid,si,sj-1,visited,'L',turns-1,ans);
}else{
helper(grid,si+1,sj,visited,'D',turns,ans);
helper(grid,si-1,sj,visited,'U',turns,ans);
helper(grid,si,sj+1,visited,'R',turns,ans);
helper(grid,si,sj-1,visited,'L',turns,ans);
}
return;
}
int main() {
int b;cin>>b;
int p;cin>>p;
vector<vector<char>> grid(b,vector<char>(p));
int si = -1;
int sj = -1;
int ei = -1;
int ej = -1;
for(int i=0; i<b; i++){
for(int j=0; j<p; j++){
cin>>grid[i][j];
// cout<<grid[i][j]<<" ";
if(grid[i][j] == 'Q'){
si = i;
sj = j;
}
if(grid[i][j] == 'W'){
ei = i;
ej = j;
}
}
// cout<<endl;
}
// cout<<si<<sj;
vector<vector<int>> visited(b,vector<int>(p));
bool ans = false;
helper(grid,si,sj,visited,'Q',2,ans);
if(ans){
cout<<"DRIVE!";
return 0;
}
cout<<"DON'T DRIVE!";
return 0;
}
Cpp
INFO