fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N=1e3+20;
  4. int t,n,i,j,k,dp[N][N],ans,cnt;
  5. char a[N][N];
  6. int dx[]={-1,-1,0};
  7. int dy[]={-1,0,-1};
  8.  
  9. bool invalid(int x,int y)
  10. {
  11. 	return min(x,y)<0 or max(x,y)>=n or a[x][y]=='X';
  12. }
  13.  
  14. int grundy(int x,int y)
  15. {
  16. 	int &ans=dp[x][y];
  17. 	if(ans!=-1) return ans;
  18.  
  19. 	set <int> s;
  20. 	for(int k=0;k<3;k++)
  21. 	{
  22. 		int nx=x+dx[k],ny=y+dy[k];
  23. 		if(invalid(nx,ny)) continue;
  24.  
  25. 		s.insert(grundy(nx,ny));
  26. 	}
  27.  
  28. 	int mex=0;
  29. 	while(s.find(mex)!=s.end()) mex++;
  30. 	return ans=mex;
  31. }
  32.  
  33. int main()
  34. {
  35. 	scanf("%d",&t);
  36. 	while(t--)
  37. 	{
  38. 		scanf("%d",&n);
  39. 		for(i=0;i<n;i++) scanf(" %s",a[i]);
  40.  
  41. 		for(i=0;i<n;i++) for(j=0;j<n;j++) dp[i][j]=-1;
  42.  
  43. 		cnt=ans=dp[0][0]=0;
  44. 		for(i=0;i<n;i++)
  45. 			for(j=0;j<n;j++)
  46. 				if(a[i][j]=='K') ans^=grundy(i,j);
  47.  
  48. 		for(i=0;i<n;i++)
  49. 		{
  50. 			for(j=0;j<n;j++)
  51. 			{
  52. 				if(a[i][j]!='K') continue;
  53.  
  54. 				for(k=0;k<3;k++)
  55. 				{
  56. 					int x=i+dx[k],y=j+dy[k];
  57. 					if(invalid(x,y)) continue;
  58.  
  59. 					if((ans^grundy(x,y)^grundy(i,j))==0) cnt++;
  60. 				}
  61. 			}
  62. 		}
  63.  
  64. 		if(ans) printf("WIN %d\n",cnt);
  65. 		else printf("LOSE\n");
  66. 	}
  67. }
Success #stdin #stdout 0s 20320KB
comments (?)
stdin 
2
2
.K
.K
2
K.
XX
stdout 
WIN 2
LOSE
https://ideone.com/o2wMUq
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!