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

Re:判断雪花是否相同,其实也不难,翻转和移动 6次 就能判断出来。

Posted by CmsMartin at 2022-03-18 19:07:42 on Problem 3349
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:
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