• 欢迎光临~

AtCoder AGC033B LRUD Game

开发技术 开发技术 2022-07-21 次浏览

洛谷传送门

AtCoder 传送门

思路

考虑正向进行操作并且维护当前棋子能到达的行区间 ([up,down]) 和列区间 ([left,right])。则先手每次将区间往外扩展一格,而后手每次尽可能将区间往内缩小。当某一时刻先手执行完操作后区间的最左端或最右端不在棋盘上了,那么输出 NO。执行完所有操作后,若区间的最左端或最右端仍然在棋盘上,输出 YES

代码

code
/*

p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy

*/

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, m, K, sx, sy;
char s[maxn], t[maxn];

void solve() {
	scanf("%d%d%d%d%d%s%s", &n, &m, &K, &sx, &sy, s + 1, t + 1);
	int up = sx, dw = sx, lf = sy, rg = sy;
	for (int i = 1; i <= K; ++i) {
		if (s[i] == 'U') {
			--up;
		} else if (s[i] == 'D') {
			++dw;
		} else if (s[i] == 'L') {
			--lf;
		} else if (s[i] == 'R') {
			++rg;
		}
		if (up < 1 || dw > n || lf < 1 || rg > m) {
			puts("NO");
			return;
		}
		if (t[i] == 'U') {
			dw = max(dw - 1, 1);
		} else if (t[i] == 'D') {
			up = min(up + 1, n);
		} else if (t[i] == 'L') {
			rg = max(rg - 1, 1);
		} else if (t[i] == 'R') {
			lf = min(lf + 1, m);
		}
	}
	puts("YES");
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:AtCoder AGC033B LRUD Game
喜欢 (0)