| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
0ms 720kb//
// main.cpp
// ACM
//
// Created by Lethorld Wang on 8/21/12.
// Copyright (c) 2012 logicsolutions. All rights reserved.
//
#include <iostream>
#include <errno.h>
typedef struct node {
int xpos;
int ypos;
node *next;
} node;
typedef struct cluster {
node *root;
node *tail;
int total;
} cluster;
typedef struct keys {
int total;
int width;
int height;
int weight;
} keys;
void dfs4cluster(bool (*board)[100], int width, int height, int xpos, int ypos, cluster *cluster);
int main(int argc, const char * argv[])
{
// freopen("/Users/shlogic/in.txt","r",stdin);
// freopen("/Users/shlogic/out.txt","w",stdout);
int testCase;
bool board[100][100];
cluster cluster1[100 * 100];
cluster cluster2[100 * 100];
keys key1[100 * 100];
keys key2[100 * 100];
scanf("%d", &testCase);
while (testCase) {
int i, j, k, xpos, ypos;;
int width, height, pointNum, clusterNum1, clusterNum2, clusterNum;
clusterNum1 = clusterNum2 = 0;
memset(cluster1, 0x00, sizeof(cluster) * 100 * 100);
memset(cluster2, 0x00, sizeof(cluster) * 100 * 100);
scanf("%d", &width);
scanf("%d", &height);
scanf("%d", &pointNum);
memset(board, 0x00, sizeof(bool) * 100 * 100);
for (i=0; i<pointNum; i++) {
scanf("%d", &xpos);
scanf("%d", &ypos);
board[xpos][ypos] = true;
}
// collect the first board's cluster.
for (i=0; i<width; i++) {
for (j=0; j<height; j++) {
if (board[i][j]) {
cluster temp;
temp.total = 0;
temp.root = NULL;
temp.tail = NULL;
dfs4cluster(board, width, height, i, j, &temp);
for (k=clusterNum1 - 1; k>=0; k--) {
if (cluster1[k].total < temp.total)
cluster1[k + 1] = cluster1[k];
else break;
}
cluster1[k + 1] = temp;
clusterNum1++;
}
}
}
memset(board, 0x00, sizeof(bool) * 100 * 100);
for (i=0; i<pointNum; i++) {
scanf("%d", &xpos);
scanf("%d", &ypos);
board[xpos][ypos] = true;
}
// collect the second board's cluster.
for (i=0; i<width; i++) {
for (j=0; j<height; j++) {
if (board[i][j]) {
cluster temp;
temp.total = 0;
temp.root = NULL;
temp.tail = NULL;
dfs4cluster(board, width, height, i, j, &temp);
for (k=clusterNum2 - 1; k>=0; k--) {
if (cluster2[k].total < temp.total)
cluster2[k + 1] = cluster2[k];
else break;
}
cluster2[k + 1] = temp;
clusterNum2++;
}
}
}
// compare the cluster number
if (clusterNum1 == clusterNum2) {
clusterNum = clusterNum1;
// check if the total value is always equal
bool check = true;
for (i=0; i<clusterNum; i++) {
if (cluster1[i].total != cluster2[i].total) {
check = false;
break;
}
}
if (!check) printf("NO\n");
else {
int left, right, top, bottom;
node *cnode;
keys ckey;
for (i=0; i<clusterNum; i++) {
left = top = 99;
bottom = right = 0;
cnode = cluster1[i].root;
while (cnode != NULL) {
if (cnode->xpos < left) left = cnode->xpos;
if (cnode->xpos > right) right = cnode->xpos;
if (cnode->ypos < top) top = cnode->ypos;
if (cnode->ypos > bottom) bottom = cnode->ypos;
cnode = cnode->next;
}
right++;
left--;
top--;
bottom++;
ckey.width = right - left - 1;
ckey.height = bottom - top - 1;
ckey.weight = 0;
cnode = cluster1[i].root;
while (cnode != NULL) {
ckey.weight += (cnode->xpos - left) * (cnode->xpos - left);
ckey.weight += (cnode->xpos - right) * (cnode->xpos - right);
ckey.weight += (cnode->ypos - top) * (cnode->ypos - top);
ckey.weight += (cnode->ypos - bottom) * (cnode->ypos - bottom);
cnode = cnode->next;
}
ckey.total = cluster1[i].total;
if (ckey.width < ckey.height) {
int temp = ckey.width;
ckey.width = ckey.height;
ckey.height = temp;
}
for (j=i-1; j>=0; j--) {
bool goon = false;
if (key1[j].total < ckey.total) {
goon = true;
}
else if (key1[j].total == ckey.total) {
if (key1[j].width < ckey.width) {
goon = true;
}
else if (key1[j].width == ckey.width) {
if (key1[j].height < ckey.height) {
goon = true;
}
else if (key1[j].height == ckey.height) {
if (key1[j].weight < ckey.weight) {
goon = true;
}
}
}
}
if (goon) key1[j + 1] = key1[j];
else break;
}
key1[j + 1] = ckey;
left = top = 99;
bottom = right = 0;
cnode = cluster2[i].root;
while (cnode != NULL) {
if (cnode->xpos < left) left = cnode->xpos;
if (cnode->xpos > right) right = cnode->xpos;
if (cnode->ypos < top) top = cnode->ypos;
if (cnode->ypos > bottom) bottom = cnode->ypos;
cnode = cnode->next;
}
right++;
left--;
top--;
bottom++;
ckey.width = right - left - 1;
ckey.height = bottom - top - 1;
ckey.weight = 0;
cnode = cluster2[i].root;
while (cnode != NULL) {
ckey.weight += (cnode->xpos - left) * (cnode->xpos - left);
ckey.weight += (cnode->xpos - right) * (cnode->xpos - right);
ckey.weight += (cnode->ypos - top) * (cnode->ypos - top);
ckey.weight += (cnode->ypos - bottom) * (cnode->ypos - bottom);
cnode = cnode->next;
}
ckey.total = cluster2[i].total;
if (ckey.width < ckey.height) {
int temp = ckey.width;
ckey.width = ckey.height;
ckey.height = temp;
}
for (j=i-1; j>=0; j--) {
bool goon = false;
if (key2[j].total < ckey.total) {
goon = true;
}
else if (key2[j].total == ckey.total) {
if (key2[j].width < ckey.width) {
goon = true;
}
else if (key2[j].width == ckey.width) {
if (key2[j].height < ckey.height) {
goon = true;
}
else if (key2[j].height == ckey.height) {
if (key2[j].weight < ckey.weight) {
goon = true;
}
}
}
}
if (goon) key2[j + 1] = key2[j];
else break;
}
key2[j + 1] = ckey;
}
bool yes = true;
for (i=0; i<clusterNum; i++) {
if (key1[i].total == key2[i].total &&
key1[i].width == key2[i].width &&
key1[i].height == key2[i].height &&
key1[i].weight == key2[i].weight) {
}
else {
yes = false;
break;
}
}
if (yes) printf("YES\n");
else printf("NO\n");
}
}
else printf("NO\n");
testCase--;
}
return 0;
}
void dfs4cluster(bool (*board)[100], int width, int height, int xpos, int ypos, cluster *cluster) {
if (xpos < 0 || ypos < 0 || xpos >= width || ypos >= height) return ;
if (board[xpos][ypos]) {
board[xpos][ypos] = false;
node *cnode = (node *)malloc(sizeof(node));
cnode->xpos = xpos;
cnode->ypos = ypos;
cnode->next = NULL;
// add to the cluster
if (cluster->root == NULL) {
cluster->root = cnode;
cluster->tail = cnode;
}
else {
cluster->tail->next = cnode;
cluster->tail = cnode;
}
cluster->total++;
dfs4cluster(board, width, height, xpos - 1, ypos, cluster);
dfs4cluster(board, width, height, xpos + 1, ypos, cluster);
dfs4cluster(board, width, height, xpos, ypos - 1, cluster);
dfs4cluster(board, width, height, xpos, ypos + 1, cluster);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator