题目大意:给出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; }