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