poj1021棋盘同构有关问题
poj1021棋盘同构问题
算模拟题吧，先把两个图的所有连通分量计算出来，然后再一一配对，有一个配对不成功便返回false，配对的过程中可旋转90，180，270，360度以及上下翻折，左右翻折。
（开始没考虑翻折，导致wa了一次，调试时才发现，然后就一次AC了，数据太弱，骗分都可以过。。。）
包括调试代码总共200+行代码。第一次刷题写这么读代码阿。。汗～
AC代码(由于数据很弱故没优化，时间有点长。。。。。。囧)：
忘了还有中心对称旋转。。。
# include <stdlib.h>
# include <string.h>
# include <stdio.h>
# define paste(x,y) x ## y
# define DEBU
int cs1[110][110];
int cs2[110][110];
int x[110][110];
int y[110][110];
int xx[] = {1,-1,0,0};
int yy[] = {0,0,-1,1};
int w,h,n,max;
int cmp() {
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
if (x[i][j] != y[i][j]) {
return 0;
}
}
}
return 1;
}
int toBound(int c) {
int t[110][110];
if (c == 1) {
memcpy(t, x, sizeof(t));
}
else {
memcpy(t, y, sizeof(t));
}
int up;
int left;
#ifdef DEBUG
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
printf ("%d ", x[i][j]);
}
printf("\n");
}
printf ("\n*************\n");
#endif
for (up = 0; up < max; ++ up) {
for (int i = 0; i < max; ++ i) {
if (t[up][i]) goto flag1;
}
}
flag1:
for (left = 0;left < max ; ++ left) {
for (int i = 0; i < max; ++ i) {
if (t[i][left]) goto flag2;
}
}
flag2:
if(left)
for (int i = left; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
t[j][i - left] = t[j][i];
t[j][i] = 0;
}
}
if(up)
for (int i = up; i < 110; ++ i) {
for (int j = 0; j < 110; ++ j) {
t[i - up][j] = t[i][j];
t[i][j] = 0;
}
}
if (c == 1) {
memcpy(x, t, sizeof(t));
}
else {
memcpy(y, t, sizeof(t));
}
#ifdef DEBUG
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
printf ("%d ", x[i][j]);
}
printf("\n");
}
printf ("\n*************\n");
#endif
return 0;
}
int up_down(){
int t[110][110];
memset(t, 0, sizeof(t));
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
t[i][j] = x[max - 1 - i][j];
}
}
memcpy(x, t, sizeof(t));
toBound(1);
return 0;
}
int left_right(){
int t[110][110];
memset(t, 0, sizeof(t));
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
t[i][j] = x[i][max - 1 - j];
}
}
memcpy(x, t, sizeof(t));
toBound(1);
return 0;
}
int rotal(){
int t[110][110];
memset(t, 0, sizeof(t));
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
t[i][j] = x[w - 1 - j][i];
}
}
memcpy(x, t, sizeof(x));
toBound(1);
return 0;
}
int dfs1(int x, int y, int color) {
int xi, yi;
cs1[x][y] = color;
for (int i = 0; i < 4; ++ i) {
xi = x + xx[i];
yi = y + yy[i];
if (xi >= 0 && xi < w && yi >= 0 && yi < h) {
if (cs1[xi][yi] == 1) {
cs1[xi][yi] = color;
dfs1(xi, yi, color);
}
}
}
return 0;
}
int dfs2(int x, int y, int color) {
int xi, yi;
cs2[x][y] = color;
for (int i = 0; i < 4; ++ i) {
xi = x + xx[i];
yi = y + yy[i];
if (xi >= 0 && xi < w && yi >= 0 && yi < h) {
if (cs2[xi][yi] == 1) {
cs2[xi][yi] = color;
dfs2(xi, yi, color);
}
}
}
return 0;
}
int check() {
int c1 = 1, c2 = 1;
for (int i = 0; i < w; ++ i) {
for (int j = 0; j < h; ++ j) {
if (cs1[i][j] == 1) {
++ c1;
dfs1(i, j, c1);
}
if (cs2[i][j] == 1) {
++ c2;
dfs2(i, j, c2);
}
}
}
#ifdef DEBU
for (int i = 0; i < max; ++ i ){
for (int j = 0; j < max; ++ j) {
printf ("%d ", cs1[i][j]);
}
printf ("\n");
}
printf ("\n");
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
printf ("%d ", cs2[i][j]);
}
printf ("\n");
}
#endif
if(c1 != c2) return 0;
for (int i = 2; i <= c1; ++ i) {
int flag = 0;
for (int j = 2; j <= c2; ++ j) {
memset (x, 0, sizeof(x));
memset (y, 0, sizeof(y));
for (int m = 0; m < w; ++ m) {
for (int n = 0; n < h; ++ n) {
if (cs1[m][n] == i) {
x[m][n] = 1;
}
if (cs2[m][n] == j) {
y[m][n] = 1;
}
}
}
toBound(2);
for (int i = 0; i < 4; ++ i) {
rotal();
if (cmp()) {
flag = 1;
break;
}
left_right();
if (cmp()) {
flag = 1;
break;
}
left_right();
up_down();
if (cmp()) {
flag = 1;
break;
}
up_down();
left_right();
up_down();
if (cmp()) {
flag = 1;
break;
}
up_down();
left_right();
}
for (int i = 0; i < 4; ++ i) {
rotal();left_right();
if (cmp()) {
flag = 1;
break;
}
}
for (int i = 0; i < 4; ++ i) {
rotal();up_down();
if (cmp()) {
flag = 1;
break;
}
}
for (int i = 0; i < 4; ++ i) {
rotal();up_down();left_right();
if (cmp()) {
flag = 1;
break;
}
}
}
if (!flag) {
#ifdef DEBU
printf ("faile at %d\n", i);
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
printf ("%d ", x[i][j]);
}
printf ("\n");
}
printf ("\n");
for (int i = 0; i < max; ++ i) {
for (int j = 0; j < max; ++ j) {
printf ("%d ", y[i][j]);
}
printf ("\n");
}
#endif
return 0;
}
}
return 1;
}
int main () {
int ts;
for (scanf("%d", &ts); ts; -- ts){
scanf("%d %d %d", &w, &h, &n);
max = w > h ? w : h;
memset (cs1, 0, sizeof(cs1));
memset (cs2, 0, sizeof(cs2));
for (int i = 0; i < n; ++ i) {
int x, y;
scanf("%d %d", &x, &y);
++ cs1[x][y];
}
for (int i = 0; i < n; ++ i) {
int x, y;
scanf("%d %d", &x, &y);
++ cs2[x][y];
}
if (check()) {
printf ("YES\n");
}
else {
printf ("NO\n");
}
}
return 0;
}