#P1021. 2D-Nim
2D-Nim
📘 题目描述(中文)
2D-Nim 是一个在二维网格上进行的博弈游戏。在网格点上放置一些棋子。每一步,玩家可以选择一行或一列,并从中移除连续的一段棋子(至少一颗)。移除最后一个棋子的人获胜。
如下图所示,某个棋盘上的棋子配置如下:
可以移除: (A),(B),(A,B),(A,B,C),(B,F) 不可以移除: (A,C),(D,E),(H,I),(B,G) 某程序员正在开发一个用于玩 2D-Nim 的软件,他需要判断两个不同棋盘上的棋子布局是否“本质相同”。注意:
棋子在棋盘上的绝对位置不重要;
关键在于相同形状的连通块(Cluster)是否存在;
每个“连通块”由若干棋子组成,这些棋子是通过上下左右相邻连接起来的。
两个棋盘等价,当且仅当它们包含完全相同的连通块集合,不考虑连通块的翻转、旋转或位移。
🧾 输入格式
第一行一个整数 ,表示测试用例数()。
每个测试用例包含:
第一行三个整数 :
:网格宽度
:网格高度
:每个棋盘上的棋子数量()
第二行 对整数:棋盘一上每个棋子的坐标 ,
第三行 对整数:棋盘二上每个棋子的坐标
📤 输出格式
每个测试用例输出一行,内容为:
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