直接暴力:
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define LL long long
#define UI unsigned int
#define inf 0x7fffffff
#define eps 1e-7
#define M 105
#define N 60
using namespace std;
int m,n,t;
struct Node
{
bool ma[N][N];
int n;
bool operator<(const Node &a)const
{
for (int i=0; i<n; ++i )
for(int j=0; j<n; ++j)
if(ma[i][j]!=a.ma[i][j])
return ma[i][j]<a.ma[i][j];
return 0;
}
};
void tran(bool ma[][N])
{
bool t[N][N];
for (int i=0; i<n; ++i )
{
for(int j=0; j<n; ++j)
{
t[j][n-i-1]=ma[i][j];
}
}
memcpy(ma,t,sizeof(t));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in","r",stdin);
#endif
while(scanf("%d",&n)==1&&n)
{
set<Node>s;
Node a;
memset(a.ma,0,sizeof(a.ma));
a.n=n;
int ok=0;
for (int i=0; i<2*n; ++i )
{
int x,y;
char c;
scanf("%d%d%*c%c",&x,&y,&c);
if(ok)continue;
x--,y--;
if(c=='+')
{
a.ma[x][y]=1;
}
else
{
a.ma[x][y]=0;
}
if(s.find(a)!=s.end())
{
printf("Player %d wins on move %d\n",i%2==0?2:1,i+1);
ok=1;
}
s.insert(a);
for(int j=0; j<3; ++j)
{
tran(a.ma);
s.insert(a);
}
tran(a.ma);
}
if(!ok)
printf("Draw\n");
}
return 0;
}
编码方法(不一定对):
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define ULL unsigned long long
#define LL long long
#define UI unsigned int
#define inf 0x7fffffff
#define eps 1e-7
#define M 105
#define N 60
using namespace std;
int m,n,t;
struct Node
{
bool ma[N][N];
int n;
};
void tran(bool ma[][N])
{
bool t[N][N];
for (int i=0; i<n; ++i )
{
for(int j=0; j<n; ++j)
{
t[j][n-i-1]=ma[i][j];
}
}
memcpy(ma,t,sizeof(t));
}
ULL fun(bool ma[][N])
{
ULL ans=0,cnt=0;
for (int i=0; i<n; ++i )
{
for(int j=0; j<n; ++j)
{
ans+=(i*(n+12345)+j*12345)*ma[i][j];
if(ma[i][j])cnt++;
}
}
return ans-cnt;;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in","r",stdin);
#endif
while(scanf("%d",&n)==1&&n)
{
set<ULL>s;
Node a;
memset(a.ma,0,sizeof(a.ma));
a.n=n;
int ok=0;
for (int i=0; i<2*n; ++i )
{
int x,y;
char c;
scanf("%d%d%*c%c",&x,&y,&c);
if(ok)continue;
x--,y--;
if(c=='+')
{
a.ma[x][y]=1;
}
else
{
a.ma[x][y]=0;
}
ULL num=fun(a.ma);
if(s.find(num)!=s.end())
{
printf("Player %d wins on move %d\n",i%2==0?2:1,i+1);
ok=1;
}
s.insert(num);
for(int j=0; j<3; ++j)
{
tran(a.ma);
s.insert(fun(a.ma));
}
tran(a.ma);
}
if(!ok)
printf("Draw\n");
}
return 0;
}