uva 141 - The Spot Game

点击打开链接

题目意思：     有两个人在玩游戏，游戏是在长为N的正方形棋盘，上面是由一序列格子组成，现在输入一些操作指令由两个人轮流操作，每一次操作对应的棋盘上面会有一个状态，如果当前的状态或这个状态旋转90或180度而来的状态以及出现过，那么这个人就输，如果当所有指令操作完以后还没分胜负就是平局

解题思路：       set+状态判重即可，注意对set里面放结构体的使用，重载<号。

1：我们知道对于set和map而言，插入的数据默认是那些常见的数据，由于set和map的内部实现是有一个cmp函数（使用小于号）的。那么如果我们要将结构体插入set或map里面，那么我们就应该在结构体里面重载一个小于号函数。（对于这一题，由于我么只是想知道到底有没有存在这个状态对于是否按照什么顺序我们不用关心，那么我么只须重载了小于<函数就可以了，并不用纠结怎么重载）

                       2：对于状态的判重，我么知道只要将初始状态一直向右旋转，那么最后还是会回到最初的状态，所以我么只要能够找到向右旋转90度后的状态和初始状态的关系，然后没得到一个状态就去判断，如果初始状态和由它旋转而来的状态都不再set里面，那么就把这些状态插入set。注意这里必须等到所有的都不再set里面再一起插入

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 55

int n;
struct state{//状态结构体
    int State[MAXN][MAXN];
    //自定义重载<(定义为友元)
    friend bool operator<(const state &a,const state &b){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){//以第一个值作为判断基准
               if(a.State[i][j] < b.State[i][j]) return true;
               if(a.State[i][j] > b.State[i][j]) return false;
            }
        } 
    }
}sta;
set<state>s;//创建set容器s

//处理
int solve(){
    state tmp1 , tmp2 , tmp3;
    if(s.find(sta) != s.end()) return 1;
    else{
        //sta右旋转90得到tmp1
        memset(tmp1.State , 0 , sizeof(tmp1.State));
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++)
                tmp1.State[j][n-i+1] = sta.State[i][j];
        }

        if(s.find(tmp1) != s.end()) return 1;//如果存在返回1
       
        //tmp1旋转90得到tmp2
        memset(tmp2.State , 0 , sizeof(tmp2.State));
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++)
                tmp2.State[j][n-i+1] = tmp1.State[i][j];
        }
        if(s.find(tmp2) != s.end()) return 1;//如果存在返回1        
        
        //tmp2旋转90得到tmp3
        memset(tmp3.State , 0 , sizeof(tmp3.State));
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= n ; j++)
                tmp3.State[j][n-i+1] = tmp2.State[i][j];
        }
        if(s.find(tmp3) != s.end()) return 1;//如果存在返回1
        //最后插入set（如果前面插入存在导致错误的判断）
        s.insert(sta)  ; s.insert(tmp1);
        s.insert(tmp2) ; s.insert(tmp3);
    }
    return 0;
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    int  G[110][2];
    char c[110];
    int  flag;//判断是否是平局还是某一方赢
    while(scanf("%d" , &n) && n){
        s.clear();
        memset(sta.State , 0 , sizeof(sta.State)) ; flag = 0;
        for(int i = 1 ; i <= 2*n ; i++)
            scanf("%d %d %c" , &G[i][0] , &G[i][1] , &c[i]);
        for(int i = 1 ; i <= 2*n ; i++){
            if(c[i] == '+') sta.State[G[i][0]][G[i][1]] = 1;
            if(c[i] == '-')   sta.State[G[i][0]][G[i][1]] = 0;
            if(i > 1){
                if(solve()){
                   if(i % 2 != 0) printf("Player 2 wins on move %d\n" , i);//注意赢家是谁
                   else printf("Player 1 wins on move %d\n" , i);
                   flag = 1 ; break;
                }
            }
            else s.insert(sta) ;//第一个状态直接插入即可
        }
        if(!flag) printf("Draw\n");
    }
    return 0;
}