首页 > 其他 > 详细

poj 3349

时间:2015-05-09 23:26:37      阅读:369      评论:0      收藏:0      [点我收藏+]

题意:每个雪花都有六个分支,用六个整数代表,这六个整数是从任意一个分支开始,朝顺时针或逆时针方向遍历得到的。输入多个雪花,判断是否有形状一致的雪花存在。

简单的数字哈希,要注意的是每种雪花可以由多种数字组合表示。

比如输入的是1 2 3 4 5 6,

则2 3 4 5 6 1,3 4  5 6 1 2,……,6 5 4 3 2 1,5 4 3 2 1 6等都是相同形状的。

如果某次插入的时候发生冲突,则说明存在重复的雪花,并且后面的不需要再处理。

这题学到了大量数据要用BufferedReader,用Scanner会超时

Memory:  10896K

Time:  9985MS

import java.util.Scanner;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;


class Node{
        int lengths[] = new int[6];
        
        Node(int lengths[]){
            this.lengths = lengths;
            Arrays.sort(lengths);
        }
        public int get(int i){
            return lengths[i];
        }
    }

public class Main{
    static int n;
    
    static boolean same(Node x,Node y){
        for(int i=0;i<6;i++){
            if(x.get(i)!=y.get(i))
                return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        int flag = 0;
        Node nodes[][] = new Node[1500][100];
        int m[] = new int[1500];
        Arrays.fill(m,0);
        while(n!=0){
            n--;
            int sum=0;
            int temp[] = new int[6];
            String[] line = bf.readLine().split(" ");
            for(int i=0;i<6;i++){
                temp[i] = Integer.parseInt(line[i]);
                sum = (sum+temp[i])%1497;
            }
            if(flag == 0){
                Node node = new Node(temp);
                for(int j=0;j<m[sum];j++){
                    if(same(node,nodes[sum][j])){
                        flag = 1;
                        break;
                    }
                }
                nodes[sum][m[sum]] = node;
                m[sum]++;
            }
        }
        if(flag == 1)
            System.out.println("Twin snowflakes found.");
        else
            System.out.println("No two snowflakes are alike.");
        bf.close();
    }
}

 

poj 3349

原文:http://www.cnblogs.com/yong-hua/p/4491329.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!