Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

0ms 720kb

Posted by lethorld at 2012-08-27 13:08:03 on Problem 1021
//
//  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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator