198B - Jumping on Walls - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, k;
vector<string> mat(2);
ll dist[2][100001];

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	
	std::cin >> n >> k >> mat[0] >> mat[1];
	memset(dist, 1, sizeof dist);
	dist[0][0] = 0;
	queue<pair<ll, ll>> q;
	q.push({0, 0});
	
	while(!q.empty()) {
		ll w = q.front().first;
		ll x = q.front().second;
		q.pop();
		
		if(dist[w][x] > x || mat[w][x] == 'X') {
			continue;
		}
		
		if(x + k >= n) {
			cout << "YES\n";
			return 0;
		}
		
		for(int d = -1; d <= 1; d++) {
			if(x + d >= 0 && 1 + dist[w][x] < dist[w][x+d]){ // subo ou desco
				dist[w][x+d] = 1 + dist[w][x];
				q.push({w, x+d});
			}
		}
		
		if(dist[!w][x+k] > 1 + dist[w][x]){ // pulo (x^1 igual a passar de 0 para 1)
			dist[!w][x+k] = 1 + dist[w][x];
			q.push({!w, x+k});
		}
	}
	cout << "NO\n";
}