---
# System prepended metadata

title: UVA-141~The Spot Game

---

UVA-141~The Spot Game 
=======
## 題目連結: [UVA-141](https://vjudge.net/problem/UVA-141)
## 題意:
>兩個人在N*N的棋盤上輪流擺放或拿取棋子，一方動作後(放置或拿取棋子)，只要出現之前出現過的的棋盤狀態`(旋轉90°、180°、270°)`；那一方就輸了，如果進行N個回合後都沒有贏家，則輸出`Draw`
## 解法:
>模擬所有狀態並用==MAP==儲存
## 程式碼:
```C++
#include <bits/stdc++.h>
using namespace std;
string arrtostr(int arr[60][60]){
	char c[4000]={0};
	for(int i=0;i<60;i++){
		for(int j=0;j<60;j++){
			c[i*60+j]=char(arr[i][j]+'0');
		}
	}
	return c;
}
int mp[60][60],n;
void rotate(){
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			swap(mp[i][j],mp[j][i]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n/2;j++){
			swap(mp[i][n-j-1],mp[i][j]);
		}
	}
}
/*
void print(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<mp[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}*/
int main(){
	while(cin>>n,n){
		map<string,int>t;
		memset(mp,0,sizeof(mp));
		int win=0,move=0,a,b;
		for(int i=1;i<=n*2;i++){
			char x;
			cin>>a>>b>>x;
			if(move!=0){
				continue;
			}
			if(x=='+'){
				mp[b-1][a-1]=1;
			}else{
				mp[b-1][a-1]=0;
			}
			if(t[arrtostr(mp)]!=0){
				win=i%2;
				move=i;
				continue;
			}
			for(int j=0;j<4;j++){
				rotate();
				t[arrtostr(mp)]=1;
			}
		}
		if(move!=0){
			if(win==1){
				cout<<"Player "<<2<<" wins on move "<<move;
			}else{
				cout<<"Player "<<1<<" wins on move "<<move;
			}
		}else{
			cout<<"Draw";
		}
		cout<<"\n";
	}
}

```