141 - The Spot Game(STL set)

时间:2022-09-11 07:38:21

141 - The Spot Game


题目大意:给出n* n的棋盘,有两个玩家,每个玩家都可以往棋盘上放棋子或是移除一个棋子,判断哪个玩家做完上述动作后的棋盘和之前相同,那这个玩家就输了。

棋盘重复包括旋转相同,光看上诉给的图示会漏了一种,分为左旋转,右旋转,180度上下旋转,加上自身一共四种。

解题思路:用stl里的set来判重,每次都把这个状态的其他相同的状态找出来,然后逐一的判断,找到相同的就做已出现重复的标志,如果都不相同就将四种状态都加入set里。


#include<stdio.h>
#include<string.h>
#include<set>
#include<string>
using namespace std;

set<string> v;
const int N = 55;
char s[4][N * N];
int temp[N][N];
int n, x, y, ch;

void solve(){

 	int k = 0, t = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			s[k][t++] = temp[i][j] + '0';
		s[k++][t] = '\0';
	
		t = 0;
	for(int i = n - 1; i >= 0; i--)
		for(int j = 0; j < n; j++)
			s[k][t++] = temp[j][i] +'0';
		s[k++][t] = '\0';
	
		t = 0;
	for(int i = 0; i < n; i++)
		for(int j = n - 1; j >= 0; j--)
			s[k][t++] = temp[j][i] + '0';
		s[k++][t] = '\0';
		
		t = 0;
	for(int i = n- 1; i >= 0; i--)
		for(int j = n - 1; j >= 0; j--)
			s[k][t++] = temp[i][j] + '0';
		s[k][t] = '\0';
}
int main(){

	int flag = 0;
	while(scanf("%d", &n), n){
	
		flag = 0;
		memset(temp, 0, sizeof(temp));
		v.clear();
		for(int i = 0; i < 2 * n; i++ ){
			scanf("%d%d %c", &x, &y, &ch);
			if(ch == '+')
				temp[x - 1][y - 1] = 1;
			else
				temp[x - 1][y - 1 ] = 0;

			solve();

			if(!flag)	
				for(int  j = 0; j < 4; j++)
					if(v.count(s[j]))
							flag = i + 1;

			if(!flag)
				for(int j = 0; j < 4; j++)
					v.insert(s[j]);
		}

		if(!flag)
			printf("Draw\n");			
		else if(flag % 2)
			printf("Player 2 wins on move %d\n", flag);
		else
			printf("Player 1 wins on move %d\n", flag);
	}
	return 0;
}