題目大意是：在一個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 閱讀(867)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：基礎/模擬 、
題目分類：數據結構