UVa 141 The Spot Game

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=111&page=show_problem&problem=77
题意：判断摆放过程中是否出现已经出现过的图案，图案可以顺时针旋转90°，180°和水平翻转。
分析：字符串哈希判重
  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 100007;
  5 
  6 char map[52][52];
  7 char temp[52][52];
  8 char temp2[52][52];
  9 bool vis[MAXN];
 10 int N;
 11 
 12 //void show( char (*str)[52] )
 13 //{
 14 //    for ( int i = 0; i < N; ++i )
 15 //    {
 16 //        for ( int j = 0; j < N; ++j )
 17 //        putchar(str[i][j]);
 18 //        puts("");
 19 //    }
 20 //}
 21 
 22 unsigned int BKDRHash( char (*str)[52] )
 23 {
 24     unsigned int seed = 31;
 25     unsigned int hash = 0;
 26 
 27     for ( int i = 0; i < N; ++i )
 28       for ( int j = 0; j < N; ++j )
 29          hash = hash * seed + str[i][j];
 30 
 31     return (hash & 0x7FFFFFFF) % MAXN;
 32 }
 33 
 34 void Rotate( char (*str)[52], char (*ttemp)[52] )
 35 {
 36     for ( int i = 0; i < N; ++i )
 37       for ( int j = 0; j < N; ++j )
 38          ttemp[ j ][ N - 1 - i ] = str[i][j];
 39    // show(str);
 40    // show(ttemp);
 41    // puts("-------------");
 42     int hash = BKDRHash( ttemp );
 43    // printf("%d\n", hash);
 44     vis[hash] = true;
 45     return;
 46 }
 47 
 48 void Reflact( char (*str)[52] )
 49 {
 50     for ( int i = 0; i < N; ++i )
 51       for ( int j = 0; j < N; ++j )
 52          temp[i][N - 1 - j] = str[i][j];
 53 
 54     int hash = BKDRHash( temp );
 55     vis[hash] = true;
 56     return;
 57 }
 58 
 59 int main()
 60 {
 61     int x, y;
 62     char ch[3];
 63     int where, who;
 64     while ( scanf( "%d", &N ), N )
 65     {
 66         bool flag = false;
 67         memset( vis, false, sizeof(vis) );
 68         memset( map, '.', sizeof(map) );
 69 
 70         for ( int i = 0; i < N * 2; ++i )
 71         {
 72             scanf("%d%d%s", &x, &y, ch);
 73             if ( !flag )
 74             {
 75                 switch( ch[0] )
 76                 {
 77                 case '+':
 78                     map[x - 1][y - 1] = '#';
 79                     break;
 80 
 81                 case '-':
 82                     map[x - 1][y - 1] = '.';
 83                     break;
 84                 }
 85                 int hash = BKDRHash( map );
 86      //           printf("%d\n", hash);
 87                 if ( vis[hash] )
 88                 {
 89                     flag = true;
 90                     where = i + 1;
 91                     if ( i % 2 ) who = 1;
 92                     else who = 2;
 93                 }
 94                 vis[hash] = true;
 95                 Rotate( map, temp );
 96                 Rotate( temp, temp2 );
 97                 Reflact( map );
 98             }
 99         }
100         if ( !flag ) puts("Draw");
101         else printf( "Player %d wins on move %d\n", who, where );
102     }
103     return 0;
104 }