CF-198B Jumping on Walls 题解

题目大意

给你两个墙，你一开始在第一面墙的最下面，你每次可以进行三种操作，向上爬一格，向下爬一格或者跳到对面的向上k格的位置。

刚开始的时候水在-1层，你每移动一次，水就上升一层，你不能进入被水覆盖的区域，问能否爬出墙。

解题思路

刚开始就被cf的标签骗了，写个最短路。。

我刚开始还发现好像可以用最短路写，写了好久写出Dijkstra，后面发现不对。。

结果一搜发现是搜索，我吐了。。

这个搜索倒是挺简单的，只是需要剪枝，走过的地方就不用在走了。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 500, INF = 1e9;
int flag = 0, vis[2][N], n, k;
char s[2][N];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

void dfs(int pos, int num, int cnt) {
	if (pos >= n || flag) {
		flag = 1; return;
	}
	if (pos <= cnt || s[num][pos] == 'X' || vis[num][pos])	return;
	vis[num][pos] = 1;
	dfs(pos + k, num ^ 1, cnt + 1);
	dfs(pos + 1, num, cnt + 1);
	dfs(pos - 1, num, cnt + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	cin >> n >> k;
	cin >> s[0] >> s[1];
	dfs(0, 0, -1);
	if (flag)	cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}