Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Created by Acka on 9/12/16.
- //
- #include <stdio.h>
- #include <memory.h>
- #include <algorithm>
- using namespace std;
- int N, M, gn[1 << 20];
- int get_grundy(int bit){
- if(0 <= gn[bit]) return gn[bit];
- int ret[30], idx = 0;
- for(int i = 0, b = 1; i < 2; i++)
- for(int j = 0; j < M; j++, b <<= 1){
- if(bit & b) continue;
- ret[idx++] = get_grundy(bit + b);
- }
- for(int i = 0, b = 1; i < M - 1; i++, b <<= 1){
- if(bit & b || bit & (b << 1) || bit & (b << M) || bit & (b << (M + 1))) continue;
- ret[idx++] = get_grundy(bit + b + (b << 1) + (b << M) + (b << (M + 1)));
- }
- sort(ret, ret + idx);
- if(ret[0]) return gn[bit] = 0;
- int g = ret[idx - 1] + 1;
- for(int i = 1; i < idx; i++)
- if(ret[i - 1] + 1 < ret[i]){
- g = ret[i - 1] + 1; break;
- }
- return gn[bit] = g;
- }
- int main()
- {
- for(int tc = 3; tc--;){
- scanf("%d %d", &N, &M);
- char map[10][11];
- for(int i = 0; i < N; i++) scanf("%s", map[i]);
- memset(gn, 0xff, sizeof(gn));
- gn[(1 << (2 * M)) - 1] = 0;
- get_grundy(0);
- int ans = 0;
- for(int i = 0; i < N; i += 2){
- int bit = 0, b = 1;
- for(int j = 0; j < 2; j++){
- if(i + j == N){ bit += (((1 << M) - 1) << M); break; }
- for(int k = 0; k < M; k++, b <<= 1)
- if(map[i + j][k] != '.') bit += b;
- }
- ans ^= gn[bit];
- }
- printf("%c\n", ans ? 'Y' : 'M');
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement