199D - Jumping on Walls - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
using namespace std;
const ll mod = 1e9 + 7;
// const ll minmod=-1e18;
const ll inf = 1e18;
 
ll min(ll a, ll b)
{
    if (a > b)
    {
        return b;
    }
    return a;
}
 
ll max(ll a, ll b)
{
    if (a > b)
    {
        return a;
    }
    return b;
}
 
ll bexpmod(ll a, ll b,ll mod)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 0)
    {
        return bexpmod((((a % mod) * (a % mod)) % mod), b / 2,mod);
    }
    return ((a % mod) * (bexpmod((((a % mod) * (a % mod)) % mod), (b - 1) / 2,mod) % mod)) % mod;
}
 
ll gcd(ll a,ll b)
{
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
 
ll mylcm(ll a,ll b)
{
    return (a*b)/gcd(a,b);
}
 
ll bexp(ll a, ll b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 0)
    {
        return bexp((a * a), b / 2);
    }
    return (a  * (bexp((a * a), (b - 1) / 2)));
}
 
ll nCr(ll n, ll k) {
    ld res = 1;
    for (ll i = 1; i <= k; ++i)
        res = res * (n - k + i) / i;
    return (ll)(res + 0.01);
}
 
string decToBin(ll num)
{
	string str;
  	while(num){
  		if(num & 1){
    		str+='1';
    	}
  		else{
    		str+='0';
    	}
  		num>>=1;
	}
	reverse(str.begin(),str.end());
	return str;
} 
 
ll binToDec(string s){
	ll num=0;
	ll pw=1;
	ll i=s.size()-1;
	while(i>=0){
		num+=((s[i]-'0')*pw);
		i--;
		pw*=2;
	}
	return num;
}
 
ll gcdEd(ll a,ll b,ll *x,ll *y){
	if(a==0){
		*x=0;
		*y=1;
		return b;
	}
	ll x1,y1;
	ll gcd1 = gcdEd(b%a,a,&x1,&y1);
	
	*x=y1-(b/a)*x1;
	*y=x1;
	
	return gcd1;
}

string u,d;

bool isSafe(ll i,ll j,ll time){
	if(i<time){
		return false;
	}
	if(j==0){
		if(u[i]=='X'){
			return false;
		}
	}
	else{
		if(d[i]=='X'){
			return false;
		}
	}
	return true;
}

void solve()
{	
	ll n,k;
	cin>>n>>k;
	cin>>u>>d;
	queue<pair<ll,ll> >q;
	q.push({0,0});
	vector<vector<ll> >time(n,vector<ll>(2,-1));
	time[0][0]=0;
	ll pos=-1;
	while(!q.empty()){
		if(pos==1){
			break;
		}
		pair<ll,ll>cur=q.front();
		q.pop();
		ll x=cur.ff;
		ll y=cur.ss;
		ll cy;
		// cout<<x<<" "<<y<<endl;
		if(y==0){
			cy=1;
		}
		else{
			cy=-1;
		}
		ll dx[3]={-1,1,k};
		ll dy[3]={0,0,cy};
		for(ll i=0;i<3;i++){
			ll nx=x+dx[i];
			ll ny=y+dy[i];
			// cout<<nx<<" "<<ny<<" "<<i<<endl;
			if(nx>=n){
				pos=1;
				break;
			}
			if(isSafe(nx,ny,time[x][y]+1)){
				// cout<<1<<endl;
				// cout<<time[nx][ny]<<endl;
				if(time[nx][ny]==-1){
					// cout<<2<<endl;
					q.push({nx,ny});
					time[nx][ny]=1+time[x][y];
				}
				else if(time[nx][ny]>1+time[x][y]){
					// cout<<3<<endl;
					q.push({nx,ny});
					time[nx][ny]=1+time[x][y];
				}
				// if(time[nx][nx]==-1){
// 					
				// }
				// else if(time[nx][ny]>1+time[x][y]){
// 					
				// }
			}
		}
	}
	if(pos==1){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    ll t = 1;
    for(ll i=1;i<=t;i++){
        // cout << "Case #"<<i<<": ";
        solve();
    }
}