Advertisement
Guest User

Untitled

a guest
Sep 27th, 2016
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. //
  2. // Created by Acka on 9/12/16.
  3. //
  4.  
  5. #include <stdio.h>
  6. #include <memory.h>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. int N, M, gn[1 << 20];
  11.  
  12. int get_grundy(int bit){
  13. if(0 <= gn[bit]) return gn[bit];
  14.  
  15. int ret[30], idx = 0;
  16. for(int i = 0, b = 1; i < 2; i++)
  17. for(int j = 0; j < M; j++, b <<= 1){
  18. if(bit & b) continue;
  19. ret[idx++] = get_grundy(bit + b);
  20. }
  21.  
  22. for(int i = 0, b = 1; i < M - 1; i++, b <<= 1){
  23. if(bit & b || bit & (b << 1) || bit & (b << M) || bit & (b << (M + 1))) continue;
  24. ret[idx++] = get_grundy(bit + b + (b << 1) + (b << M) + (b << (M + 1)));
  25. }
  26.  
  27. sort(ret, ret + idx);
  28. if(ret[0]) return gn[bit] = 0;
  29.  
  30. int g = ret[idx - 1] + 1;
  31. for(int i = 1; i < idx; i++)
  32. if(ret[i - 1] + 1 < ret[i]){
  33. g = ret[i - 1] + 1; break;
  34. }
  35.  
  36. return gn[bit] = g;
  37. }
  38.  
  39. int main()
  40. {
  41. for(int tc = 3; tc--;){
  42. scanf("%d %d", &N, &M);
  43.  
  44. char map[10][11];
  45. for(int i = 0; i < N; i++) scanf("%s", map[i]);
  46.  
  47. memset(gn, 0xff, sizeof(gn));
  48. gn[(1 << (2 * M)) - 1] = 0;
  49. get_grundy(0);
  50.  
  51. int ans = 0;
  52. for(int i = 0; i < N; i += 2){
  53. int bit = 0, b = 1;
  54. for(int j = 0; j < 2; j++){
  55. if(i + j == N){ bit += (((1 << M) - 1) << M); break; }
  56. for(int k = 0; k < M; k++, b <<= 1)
  57. if(map[i + j][k] != '.') bit += b;
  58. }
  59. ans ^= gn[bit];
  60. }
  61.  
  62. printf("%c\n", ans ? 'Y' : 'M');
  63. }
  64. return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement