牛客多校第6场M(dp或者递推)

 思路:首先,我们可以将整个地图看成一个棋盘,起点为白色,然后(x + y)为偶时是Alice走,否则是Bob走.然后,倒着递推,假设f[i][j]为棋子在坐标(i, j)时的胜负情况,用一个二进制数表示,从低到高为分别表示平局,A赢,B赢.我们考虑只对Alice所走的路径进行dp,由于我们要考虑Bob的所有举动,所以这些胜负情况要先取与,取完与后状态仍然为1说明无论这一步Bob怎么走,都不会影响状态,此时我们取或.最后输出起点的答案即可.

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 510;
int n, m, f[N][N], a[N][N];
char g[N][N];
void solve() {
	qio >> n >> m;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) f[i][j] = 0;
	for (int i = 1; i <= n; ++i) {
		qio >> g[i] + 1;
		for (int j = 1; j <= m; ++j) 
			if (g[i][j] == '.') a[i][j] = 0;
			else if (g[i][j] == 'A') a[i][j] = 1;
			else if (g[i][j] == 'B') a[i][j] = 2;
	}
	f[n][m] = f[n - 1][m] = f[n][m - 1] = (1 << a[n][m]);
	if (a[n - 1][m]) f[n - 1][m] = (1 << a[n - 1][m]);
	if (a[n][m - 1]) f[n][m - 1] = (1 << a[n][m - 1]);
	for (int i = n; i; --i) {
		for (int j = m; j; --j) {
			if (i + j >= n + m - 1 || (i + j) & 1) continue;
			if (a[i][j]) {f[i][j] = 1 << a[i][j]; continue;}
			if (i < n) {
				if (a[i + 1][j]) f[i][j] |= 1 << a[i + 1][j];
				else {
					int x1 = 7, x2 = 7;
					if (i + 2 <= n) x1 = f[i + 2][j];
					if (j + 1 <= m) x2 = f[i + 1][j + 1];
					f[i][j] |= x1 & x2;
				}
			}
			if (j < m) {
				if (a[i][j + 1]) f[i][j] |= 1 << a[i][j + 1];
				else {
					int x1 = 7, x2 = 7;
					if (j + 2 <= m) x1 = f[i][j + 2];
					if (i + 1 <= n) x2 = f[i + 1][j + 1];
					f[i][j] |= x1 & x2;
				}
			}
		}
	}
	for (int x : {1, 0, 2}) qio << (f[1][1] >> x & 1 ? "yes" : "no") << " ";
	qio << "\n";
}
signed main() {
	int T = 1;
	qio >> T;
	while (T--) solve();
}