#P1021. 2D-Nim

    ID: 22 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>Tehran 2002First Iran Nationwide Internet Programming Contest图论

2D-Nim

📘 题目描述(中文)

2D-Nim 是一个在二维网格上进行的博弈游戏。在网格点上放置一些棋子。每一步,玩家可以选择一行或一列,并从中移除连续的一段棋子(至少一颗)。移除最后一个棋子的人获胜。

如下图所示,某个棋盘上的棋子配置如下:

可以移除: (A),(B),(A,B),(A,B,C),(B,F) 不可以移除: (A,C),(D,E),(H,I),(B,G) 某程序员正在开发一个用于玩 2D-Nim 的软件,他需要判断两个不同棋盘上的棋子布局是否“本质相同”。注意:

棋子在棋盘上的绝对位置不重要;

关键在于相同形状的连通块(Cluster)是否存在;

每个“连通块”由若干棋子组成,这些棋子是通过上下左右相邻连接起来的。

两个棋盘等价,当且仅当它们包含完全相同的连通块集合,不考虑连通块的翻转、旋转或位移。

🧾 输入格式

第一行一个整数 tt,表示测试用例数(1t101 \leq t \leq 10)。

每个测试用例包含:

第一行三个整数 W,H,nW, H, n

WW:网格宽度

HH:网格高度

nn:每个棋盘上的棋子数量(1W,H1001 \leq W,H \leq 100

第二行 nn 对整数:棋盘一上每个棋子的坐标 (xi,yi)(x_i, y_i)0xi<W,0yi<H0 \le x_i < W, 0 \le y_i < H

第三行 nn 对整数:棋盘二上每个棋子的坐标 (xi,yi)(x_i, y_i)

📤 输出格式

每个测试用例输出一行,内容为:

YES:若两个棋盘等价

NO:否则

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
YES
NO