题目大意是：在一个n×n棋盘上不断执行加入棋子或移除棋子的操作，判断在哪一步出现了之前出现过的局面（通过旋转可以得到的认为是同一个局面）。
用一个set来存储已经出现过的局面，每次得到一个新局面，把这个新局面的各种旋转一起加入到set中。
以下是我的代码：
#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(57);
int n;
struct Type
{
bool r[kMaxn][kMaxn];
};
bool operator<(const Type &a,const Type &b)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a.r[i][j]<b.r[i][j])
return true;
else if(a.r[i][j]>b.r[i][j])
return false;
return false;
}
void rotate(Type &x)
{
Type t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t.r[j][n-i+1]=x.r[i][j];
x=t;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
while(scanf("%d",&n)==1 && n)
{
int ans(-1);
Type g;
set<Type> used;
memset(g.r,false,kMaxn*kMaxn*sizeof(bool));
for(int i=1;i<=2*n;i++)
{
int x,y;
char ch;
scanf("%d%d %c",&x,&y,&ch);
if(ans!=-1)
continue;
if(ch=='+')
g.r[x][y]=true;
else
g.r[x][y]=false;
if(used.count(g))
{
ans=i;
continue;
}
Type t(g);
for(int j=1;j<=4;j++)
{
used.insert(t);
rotate(t);
}
}
if(ans==-1)
printf("Draw\n");
else if(ans&1)
printf("Player 2 wins on move %d\n",ans);
else
printf("Player 1 wins on move %d\n",ans);
}
return 0;
}
posted on 2011-05-09 11:40
lee1r 阅读(827)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：基础/模拟 、
题目分类：数据结构