UVa 141 The Spot Game

题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=77

类型： 哈希判重 + 模拟

原题：

The game of Spot is played on an NxN board as shown below for N = 4. During the game, alternate players may either place a black counter (spot) in an empty square or remove one from the board, thus producing a variety of patterns. If a board pattern (or its rotation by 90 degrees or 180 degrees) is repeated during a game, the player producing that pattern loses and the other player wins. The game terminates in a draw after 2N moves if no duplicate pattern is produced before then.

Consider the following patterns:

If the first pattern had been produced earlier, then any of the following three patterns (plus one other not shown) would terminate the game, whereas the last one would not.

Input and Output

Input will consist of a series of games, each consisting of the size of the board, N (2N50) followed, on separate lines, by 2N moves, whether they are all necessary or not. Each move will consist of the coordinates of a square (integers in the range 1..N) followed by a blank and a character `+' or `-' indicating the addition or removal of a spot respectively. You may assume that all moves are legal, that is there will never be an attempt to place a spot on an occupied square, nor to remove a non-existent spot. Input will be terminated by a zero (0).

Output will consist of one line for each game indicating which player won and on which move, or that the game ended in a draw.

Sample input

2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0

Sample output

Player 2 wins on move 3
Draw

题目大意：

有一个在N*N棋盘上玩的游戏叫做Spot, 它由两个玩家轮流在棋盘上放置棋子或移除棋子， 一旦其中一个玩家放置或者移除棋子之后，那个棋盘的摆放状态或者这个转台旋转90度，180度是之前是出现过的，那么他就输了。

分析与总结：

看了下我做这题的提交记录， 一共WA了17次

到底是什么原因使得这并不难题的一题让我WA得彻底恶心了？让我们走近科学。

让我WA的原因：

1. 棋盘并不是4*4的，而是N*N的。 WA了n次。

2. 旋转问题。 题目其实说得有点含糊，只是说旋转90度和180度。 我就以为共有4种状态要判断之前是否出现过，但是题目上又说了(plus one other not shown) ，也就是说其实还有一个状态没有给出图像。 还有一个是什么呢？ 于是把题目给的图像通过旋转函数打印了出来， 发现最后一副图是不一样的，通过旋转方向根本就得不到。 这幅图实际上是第一个的镜面反射的图。 所以题目说的还有一个没有显示出来的，是旋转180度的那个图像。 因为这个原因又WA了n次。

这样的错误说明我读题还是太浮躁了，沉不下心来好好读懂题意，看了个大概知道了原理和思路就直接做了，以后一定要改掉这个习惯。

纠正了这两个错误后， 成功AC。

/*
 *  UVa  141 - The Spot Game 
 *  Time: 0.044s (UVa)
 *  Author: D_Double
 *
 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef int State[52][52];
State board, que[105];
const int HashSize = (1<<16);
int N, nState, flag, head[HashSize], next[HashSize];

// 模拟得出旋转后的状态
inline void rotate(State &next, State &s, int dir){
    if(!dir) return;
    if(dir==1){ // 顺时针90度
        for(int i=0, x=0; i<N; ++i, ++x){
            for(int j=N-1, y=0; j>=0; --j, ++y)
                next[x][y] = s[j][i];
        }
    }
    else if(dir==2){ // 逆时针90度
        for(int i=N-1, x=0; i>=0; --i, ++x){
            for(int j=0, y=0; j<N; ++j, ++y)
                next[x][y] = s[j][i];
        }
    }
    else if(dir==3){ // 180度
        for(int i=N-1, x=0; i>=0; --i, ++x){
            for(int j=N-1, y=0; j>=0; --j, ++y )
                next[x][y] = s[i][j];
        } 
    }
    else if(dir==4){ // 镜面反射
        for(int i=0, x=0; i<N; ++i, ++x){
            for(int j=N-1, y=0; j>=0; --j, ++y)
                next[x][y] = s[i][j];
        }  
    }
}

inline int hash(State &s){
    int v=0;
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            v = ((v<<1)+s[i][j]) % HashSize;
    return v%HashSize;
}
int search(State &s){
    int h=hash(s);
    int u=head[h];
    while(u){
        if(memcmp(que[u], s, sizeof(s))==0) return 1;
        u = next[u];
    }
    return 0;
}
inline void insert(int s){
    int h=hash(que[s]);
    int u=head[h];
    while(u){
        u = next[u];
    }
    next[s] = head[h] ;
    head[h] = s;
} 

bool add_hash(int s){
    State state[5];
    memcpy(state[0], que[s], sizeof(que[s]));
    for(int i=0; i<=4; ++i){
        rotate(state[i], que[s], i);
        if(search(state[i])) return false; 
    }
    insert(s); 
    return true;
}

inline void init(){
    nState = 2;
    memset(head, 0, sizeof(head));
    memset(board, 0, sizeof(board));
    memcpy(que[1], board, sizeof(board));
    insert(1);
    flag=0;
}

int main(){
    int a, b, winner, step;
    char ch;
  
    while(scanf("%d", &N), N){

        init();

        for(int i=0; i<2*N; ++i){
            scanf("%d %d %c",&a,&b,&ch);
            if(ch=='+') board[a-1][b-1] = 1;
            else board[a-1][b-1] = 0;
            memcpy(que[nState], board, sizeof(board));
            if(!flag && !add_hash(nState)){
                winner = !(i&1);  step = i+1; flag=1;
            }
            ++nState;
        }

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

—— 生命的意义，在于赋予它意义。
    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)