poj 1021 2D-Nim

2D-Nim

Description

The 2D-Nim board game is played on a grid, with pieces on the grid points. On each move, a player may remove any positive number of contiguous pieces in any row or column. The player who removes the last piece wins. For example, consider the left grid in the following figure.

The player on move may remove (A), (B), (A, B), (A, B, C), or (B,F), etc., but may not remove (A, C), (D, E), (H, I) or (B, G).
For purposes of writing 2D-Nim-playing software, a certain programmer wants to be able to tell whether or not a certain position has ever been analyzed previously. Because of the rules of 2D-Nim, it should be clear that the two boards above are essentially equivalent. That is, if there is a winning strategy for the left board, the same one must apply to the right board. The fact that the contiguous groups of pieces appear in different places and orientations is clearly irrelevant. All that matters is that the same clusters of pieces (a cluster being a set of contiguous pieces that can be reached from each other by a sequence of one-square vertical or horizontal moves) appear in each. For example, the cluster of pieces (A, B, C, F, G) appears on both boards, but it has been reflected (swapping left and right), rotated, and moved. Your task is to determine whether two given board states are equivalent in this sense or not.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. The first line of each test case consists of three integers W, H, and n (1 ≤ W, H ≤ 100). W is the width, and H is the height of the grid in terms of the number of grid points. n is the number of pieces on each board. The second line of each test case contains a sequence of n pairs of integers xi , yi, giving the coordinates of the pieces on the first board (0 ≤ xi < W and 0 ≤ yi < H). The third line of the test case describes the coordinates of the pieces on the second board in the same format.

Output

Your program should produce a single line for each test case containing a word YES or NO indicating whether the two boards are equivalent or not.

Sample Input

2
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 5 2 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 6 1 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4

Sample Output

YES
NO

2 d-nim

内存限制:10000K

参赛作品总数:4671篇，接受作品2138篇

描述

2D-Nim棋盘游戏是在网格上玩的，棋子在网格点上。在每次移动中，玩家可以移除任意正数的连续棋子。移走最后一个棋子的玩家获胜。例如，考虑下图中左边的网格。

移动中的棋手可以移走(A)、(B)、(A, B)、(A, B, C)或(B,F)等，但不能移走(A, C)、(D, E)、(H, I)或(B, G)。

为了编写2d - nimd -playing软件，某个程序员希望能够知道某个位置是否曾经被分析过。因为2D-Nim的规则，很明显上面的两个板本质上是等价的。也就是说，如果左侧棋盘有获胜的策略，那么右侧棋盘也必须采用相同的策略。这些连续的片段出现在不同的地方和方向，这一事实显然是不相干的。唯一重要的是，相同的碎片集群(集群是一组相邻的碎片，可以通过一系列垂直或水平移动相互到达)出现在每一个中。例如，碎片集群(A, B, C, F, G)出现在两个板上，但它被反射(向左和向右交换)，旋转和移动。您的任务是确定两个给定的板状态在这个意义上是否等价。

输入

输入文件的第一行包含单个整数t(1≤t≤10)，测试用例的数量，后面是每个测试用例的输入数据。每个测试用例的第一行由三个整数W、H和n(1≤W, H≤100)组成。W是宽度，H是网格的高度，用网格点的数量表示。N是每块板上的棋子数。每个测试用例都包含一个序列的二线n对整数xi,咦,给作品第一次董事会的坐标(0≤< W和0≤yj < H)。测试用例描述的第三行第二次董事会上的碎片的坐标相同的格式。

输出

您的程序应该为每个测试用例生成一行，其中包含一个单词YES或NO，指示这两个板是否等效。

Sample Input

2
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 5 2 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 6 1 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4

Sample Output

YES
NO

题目解析：

图论 讨论图的同构

主要是计算图的哈希，当两个图的哈希相同时认为图同构。

关于哈希，网上有各种版本，各个点到与他连通的点的距离的平方，各个点向四个方向可以走的步数（旁边有点则可以走），同一连通图中所有点的距离之和

这里采用比较简单的第二种，不过暂时还不知道证明方法

代码：

#include
#include
#include
using namespace std;

struct pos{
    int x;
    int y;
};

int T;
int w,h,n;
int map[105][105];
int hash[2][10005];
pos p[10005];
bool flag;

int main(){
    cin>>T;
    while(T--){
        cin>>w>>h>>n;
        memset(hash,0,sizeof(hash));
        memset(map,0,sizeof(map));
        for(int i=0;i            cin>>p[i].x>>p[i].y;
            map[p[i].x][p[i].y]=1;
        }
        for(int i=0;i            int xx=p[i].x;
            int yy=p[i].y;
            for(int x=xx+1;x            for(int x=xx-1;x>=0&&map[x][yy];x--){hash[0][i]++;}
            for(int y=yy+1;y            for(int y=yy-1;y>=0&&map[xx][y];y--){hash[0][i]++;}
        }
        memset(map,0,sizeof(map));
        for(int i=0;i            cin>>p[i].x>>p[i].y;
            map[p[i].x][p[i].y]=1;
        }
        for(int i=0;i            int xx=p[i].x;
            int yy=p[i].y;
            for(int x=xx+1;x            for(int x=xx-1;x>=0&&map[x][yy];x--){hash[1][i]++;}
            for(int y=yy+1;y            for(int y=yy-1;y>=0&&map[xx][y];y--){hash[1][i]++;}
        }
        sort(hash[0],hash[0]+n);
        sort(hash[1],hash[1]+n);
        flag=true;
        for(int i=0;i            if(hash[0][i]!=hash[1][i]){
                flag=false;
                break;
            }
        }
        if(flag){
            cout<<"YES"<        }
        else{
            cout<<"NO"<        }
    }
}