【Codeforces 138D】World of Darkraft

题目链接

题目大意

题解

#include<algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <set> using namespace std; #define rep(i, l, r) for(register int i = (l); i <= (r); i++) const int N = 50; int n, m; char s[N][N], a[N][N]; int b[N][N][2], f[N][N][N][N][2]; int dfs(int l1, int r1, int l2, int r2, int d){ if(l1 > l2 || r1 > r2) return 0; else if(f[l1][r1][l2][r2][d] != -1) return f[l1][r1][l2][r2][d]; int &ff = f[l1][r1][l2][r2][d]; ff = 0; set<int> sg; rep(i, l1, l2) rep(j, r1, r2) if((j & 1) == d){ if(a[i][j] == 'L') sg.insert(dfs(l1, r1, i-1, r2, d) ^ dfs(i+1, r1, l2, r2, d)); if(a[i][j] == 'R') sg.insert(dfs(l1, r1, l2, j-1, d) ^ dfs(l1, j+1, l2, r2, d)); if(a[i][j] == 'X') sg.insert(dfs(l1, r1, i-1, j-1, d) ^ dfs(l1, j+1, i-1, r2, d) ^ dfs(i+1, r1, l2, j-1, d) ^ dfs(i+1, j+1, l2, r2, d)); } while(sg.count(ff)) ff++; return ff; } void work(){ while(~scanf("%d%d", &n, &m)){ rep(i, 1, n) scanf("%s", s[i]+1); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(f, -1, sizeof(f)); b[1][1][0] = 1; b[1][1][1] = n; rep(i, 2, n) b[i][1][0] = b[i-1][1][0] + 1, b[i][1][1] = b[i-1][1][1] - 1; rep(j, 2, m) b[1][j][0] = b[1][j-1][0] + 1, b[1][j][1] = b[1][j-1][1] + 1; rep(i, 2, n) rep(j, 2, m) b[i][j][0] = b[i][j-1][0] + 1, b[i][j][1] = b[i][j-1][1] + 1; rep(i, 1, n) rep(j, 1, m) a[b[i][j][0]][b[i][j][1]] = s[i][j]; if(dfs(1, 1, n + m - 1, n + m - 1, 0) ^ dfs(1, 1, n + m - 1, n + m - 1, 1)) puts("WIN"); else puts("LOSE"); } } int main(){ work(); return 0; }