🧠 题解分析

🧩 问题本质：

判断两个由点集合构成的图形是否“结构相同”，即：

每个图形由若干个连通块组成

每个连通块内部棋子是通过上下左右连接的

忽略每个连通块在棋盘上的绝对位置、旋转或翻转方向

🎯 目标：

判断两个棋盘是否拥有相同的连通块集合，其中每个连通块允许：

平移

翻转（左右、上下）

旋转（90°, 180°, 270°）

🔍 具体做法

✅ 步骤一：提取连通块

对每个棋盘，使用 DFS 或 BFS 找到所有连通块

每个连通块是一个点集，如 [(1,1), (1,2), (1,3)]

✅ 步骤二：标准化连通块

将每个连通块转换为“标准形式”，便于比较

如何标准化一个连通块？ 对该连通块执行所有的旋转与翻转（共 8 种），然后：

将每个形式平移到原点（即左上角坐标为 $(0,0)$）

将坐标排序后形成元组形式

在所有标准形式中取字典序最小的一个作为该连通块的“签名”

✅ 步骤三：比较两个棋盘的连通块集合

将两个棋盘的标准化连通块集合分别计数（可用 multiset 或 Counter）

如果两个集合完全相等 → 输出 YES，否则输出 NO

🧮 时间复杂度分析

连通块搜索：$O(n)$ 次 DFS，$n \leq 10,000$

8种变换 × 每块最多几十个点，处理开销可接受

最终比对 multiset，$O(K \log K)$

✅ 总结

本题关键考点在于：

连通块的搜索（图遍历）

图形归一化（形状等价判定）

多重集合比较

代码实现

#define ll long long
#define IO ios::sync_with_stdio(false)

#include<map>
#include<queue>
#include<math.h>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
class Node{
public:
	int x,y;
};
Node node[10005];int hash1[10005],hash2[1005];
int matri[105][105];bool vis[105][105];
int w,h,num,len,len1,len2;int to[4][2]={1,0,-1,0,0,1,0,-1};
void init()
{
	memset(matri,0,sizeof(matri));
	memset(vis,0,sizeof(vis));
	len1=len2=0;
}
bool judge(int x,int y)
{
	if(x>=0&&x<w&&y>=0&&y<h&&matri[x][y]&&(!vis[x][y]))
		return true;
	return false;
}
int dis(Node a,Node b)
{
	return pow(a.x-b.x,2)+pow(a.y-b.y,2);
}
void bfs(int x,int y,int ju)
{
	Node beg,nex;len=0;
	queue<Node>way;
	beg.x=x,beg.y=y;
	way.push(beg);
	vis[x][y]=1;
	node[len++]=beg;
	while(!way.empty())
	{
		beg=way.front();
		way.pop();
		for(int i=0;i<4;i++)
		{
			nex.x=beg.x+to[i][0];
			nex.y=beg.y+to[i][1];
			if(judge(nex.x,nex.y))
			{
				way.push(nex);
				vis[nex.x][nex.y]=1;
				node[len++]=nex;
			}
		}
	}
	for(int i=0;i<len;i++)
		for(int j=0;j<len;j++)
		{
			if(ju)hash1[len1++]=dis(node[i],node[j]);
			else hash2[len2++]=dis(node[i],node[j]);
		}
}
bool ans()
{
	if(len1!=len2)return false;
	else
	{
		sort(hash1,hash1+len1);
		sort(hash2,hash2+len2);
		for(int i=0;i<len1;i++)
		{
			if(hash1[i]!=hash2[i])return false;
		}
		return true;
	}
}
int main()
{
	int t;
	scanf("%d",&t);int x,y;
	while(t--)
	{
		init();
		scanf("%d%d%d",&w,&h,&num);
		for(int i=0;i<num;i++)
		{
			scanf("%d%d",&x,&y);
			matri[x][y]=1;
		}
		for(int i=0;i<w;i++)
			for(int j=0;j<h;j++)
				if(matri[i][j]&&(!vis[i][j]))
					bfs(i,j,1);
		memset(matri,0,sizeof(matri));
		memset(vis,0,sizeof(vis));
		for(int i=0;i<num;i++)
		{
			scanf("%d%d",&x,&y);
			matri[x][y]=1;
		}
		for(int i=0;i<w;i++)
			for(int j=0;j<h;j++)
				if(matri[i][j]&&(!vis[i][j]))
					bfs(i,j,0);
		
		if(ans())cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}