380
poj 1021 2D-Nim 圖論
判斷點陣是否是同構，亂搞了個·n^3的方法，就是判斷每個點到四周的距離，然後記錄下來，排個序，如果兩個完全一樣則為YES，否則為NO。
應該在dfs上加優化就可以降到n^2.但感覺意義不大
一開始WA了2次，最後發現時結構體的構造函數沒有初始化
/*
author:jxy
lang:C/C++
university:China,Xidian Unkjiversity
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int dir[4][2]={0,1,1,0,0,-1,-1,0};
int w,h,n;
int org[102][102];
struct node
{
int d[4];
node(int *p)
{
memcpy(d,p,4*sizeof(int));
if(d[0]+d[2]>d[1]+d[3])
{
swap(d[0],d[1]);
swap(d[2],d[3]);
}
if(d[1]>d[3])swap(d[1],d[3]);
if(d[0]>d[2])swap(d[0],d[2]);
}
bool operator <(const node &a) const
{
for(int i=0;i<4;i++)
{
if(d[i]<a.d[i])return 1;
if(d[i]>a.d[i])return 0;
}
return 1;
}
bool operator ==(const node &a) const
{
return memcmp(d,a.d,4*sizeof(int))==0;
}
};
vector<node> line[2];
int flag=0;
int dfs(int &x,int &y)
{
int d[4];
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0],ty=y+dir[i][1];
d[i]=0;
while(org[tx][ty])
{
d[i]++;
tx+=dir[i][0];ty+=dir[i][1];
}
}
if(d[1]+d[3]&&d[0]+d[2])
{
line[flag].push_back(node(d));
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
line[0].clear();
line[1].clear();
scanf("%d%d%d",&w,&h,&n);
int i,j,x,y;
memset(org,0,sizeof(org));
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
org[x][y]=1;
}
flag=0;
for(i=1;i<=w;i++)
for(j=1;j<=h;j++)
{
if(org[i][j])dfs(i,j);
}
memset(org,0,sizeof(org));
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
org[x][y]=1;
}
flag=1;
for(i=1;i<=w;i++)
for(j=1;j<=h;j++)
{
if(org[i][j])dfs(i,j);
}
sort(line[0].begin(),line[0].end());
sort(line[1].begin(),line[1].end());
if(line[0]==line[1])
{
puts("YES");
}
else puts("NO");
}
}
最後更新：2017-04-03 15:22:09