➤ Problem Link : 198B. Jumping on Walls
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
char lefty[100001];
char righty[100001];
bool flag=0;
void dfs(int v,bool wall,bool visitl[],bool visitr[],int n,int time,int k)
{
cout<<v<<" "<<wall<<endl;
if(v+k>n)
{
flag=1;
return;
}
if(!wall)
{
if(!visitl[v+1] && lefty[v+1]!='X')
{
visitl[v+1]=1;
dfs(v+1,wall,visitl,visitr,n,time+1,k);
}
if(!visitl[v-1] && lefty[v-1]!='X' && v-1>time+1)
{
visitl[v-1]=1;
dfs(v-1,wall,visitl,visitr,n,time+1,k);
}
if(!visitr[v+k] && righty[v+k]!='X')
{
visitr[v+k]=1;
dfs(v+k,1,visitl,visitr,n,time+1,k);
}
}
else
{
if(!visitr[v+1] && righty[v+1]!='X')
{
visitr[v+1]=1;
dfs(v+1,wall,visitl,visitr,n,time+1,k);
}
if(!visitr[v-1] && righty[v-1]!='X' && v-1>time+1)
{
visitr[v-1]=1;
dfs(v-1,wall,visitl,visitr,n,time+1,k);
}
if(!visitl[v+k] && lefty[v+k]!='X')
{
visitl[v+k]=1;
dfs(v+k,0,visitl,visitr,n,time+1,k);
}
}
}
void bfs(int v,bool wall,bool visitl[],bool visitr[],int n,int time,int k)
{
time=0;
queue<pair<int,int> >q;
q.push(make_pair(1,0));
while(!q.empty())
{
int size=q.size();
while(size--)
{
int v = q.front().first;
wall=q.front().second;
q.pop();
if(v+k>n)
{
flag=1;
return;
}
if(!wall)
{
if(!visitl[v+1] && lefty[v+1]!='X')
{
visitl[v+1]=1;
q.push(make_pair(v+1,0));
}
if(!visitl[v-1] && lefty[v-1]!='X' && v-1>time+1)
{
visitl[v-1]=1;
q.push(make_pair(v-1,0));
}
if(!visitr[v+k] && righty[v+k]!='X')
{
visitr[v+k]=1;
q.push(make_pair(v+k,1));
}
}
else
{
if(!visitr[v+1] && righty[v+1]!='X')
{
visitr[v+1]=1;
q.push(make_pair(v+1,1));
}
if(!visitr[v-1] && righty[v-1]!='X' && v-1>time+1)
{
visitr[v-1]=1;
q.push(make_pair(v-1,1));
}
if(!visitl[v+k] && lefty[v+k]!='X')
{
visitl[v+k]=1;
q.push(make_pair(v+k,0));
}
}
}
time++;
}
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>lefty[i];
for(int i=1;i<=n;i++)
cin>>righty[i];
bool visitl[n+1]={0},visitr[n+1]={0};
visitl[1]=1;
bfs(1,0,visitl,visitr,n,0,k);
if(flag)
cout<<"YES";
else
cout<<"NO";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.