| ||||||||||
| 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 | |||||||||
Re:判断雪花是否相同,其实也不难,翻转和移动 6次 就能判断出来。In Reply To:判断雪花是否相同,其实也不难,翻转和移动 6次 就能判断出来。 Posted by:tangguojun at 2017-09-27 23:57:41 > #include<stdio.h>
> #include<algorithm>
> using namespace std;
> int n;
> struct node{
> int data[6];
> int sum;
> };
> node A[100000];
> bool cmp(node a,node b)
> {
> if(a.sum<b.sum)
> return true;
> else
> return false;
> }
>
> void move(int t[])
> {
> int temp=t[0];
> t[0]=t[1];
> t[1]=t[2];
> t[2]=t[3];
> t[3]=t[4];
> t[4]=t[5];
> t[5]=temp;
> }
> void turned(int t[])
> {//1---5 swap
> int t1=t[1];
> t[1]=t[5];
> t[5]=t1;
> //2----4 swap
> int t2=t[2];
> t[2]=t[4];
> t[4]=t2;
> }
>
> bool isthesame(int t1[],int t2[])
> {
> for(int i=0;i<6;i++)
> if(t1[i]!=t2[i])
> return false;
>
> return true;
> }
> bool same(int i,int j)
> {
> //find min
> int temp1[6],temp2[6],temp3[6],temp4[6];
> int min_index=0;
> for(int k=0;k<6;k++)
> {temp3[k]=temp1[k]=A[i].data[k];
> temp4[k]=temp2[k]=A[j].data[k];
> }
> sort(temp1,temp1+6);
> sort(temp2,temp2+6);
> for(int k=0;k<6;k++)
> {
> if(temp1[k]!=temp2[k])
> return false;
>
> }
>
> //构成的数字都相同
> //逐个比较
> int cnt=0;
> while(cnt<6)
> { if(!isthesame( temp3,temp4))
> { turned(temp3) ;
> if(!isthesame( temp3,temp4))
> { turned(temp3) ;
> move(temp3);
> }
> else
> return true ;
> }
> else
> return true;
> cnt++;
> }
> return false;
> }
> int main()
> {
> scanf("%d",&n);
> for(int i=0;i<n;i++)
> {
> scanf("%d%d%d%d%d%d",&A[i].data[0],&A[i].data[1],&A[i].data[2],&A[i].data[3],&A[i].data[4],&A[i].data[5]);
> A[i].sum=A[i].data[0]+A[i].data[1]+A[i].data[2]+A[i].data[3]+A[i].data[4]+A[i].data[5];
> }
> sort(A,A+n,cmp);
>
> int start=0 ;
> while(start<n)
> { int target=A[start].sum;
> int end=-1;
> for(int i=start;i<n;i++)
> {
> if(A[i].sum!=target)
> {
> end=i-1;
> break;
> }
> }
>
> if(end==-1)
> end=n-1;//[start,end]有无相同雪花
> if(start<end)//2以上
> {
> for(int j=start;j<end;j++)
> {
> for(int k=j+1;k<=end;k++)
> {
> if(same(j,k))
> {
> printf("Twin snowflakes found.\n");
> return 0;
> }
> }
> }
> }
>
> start=end+1;
>
>
>
> }
> printf("No two snowflakes are alike.\n");
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator