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

TLE!!AAAAAAAAA居然TLE了!!!!!!!!!求教育

Posted by 1101030124 at 2012-05-05 10:40:12 on Problem 1753
#include<stdio.h>
int B[5][5];
char str[5][5];
int min=100;
int finished()
 { 
 	 int sum=0;
 	 for (int i=0;i<4;i++)  
 	 for (int j=0;j<4;j++)   
 	 sum+=B[i][j]; 
 	 if (sum%16||sum==0)  
 	 return 0; 
 	 else  
 	 return 1;
  }
void fanzhuan1(int *n)
{
	*n=-(*n);
}
void fanzhuan(int n)
{
	n--;
	fanzhuan1(&B[n/4][n%4]);
	if(n%4+1<4)
	fanzhuan1(&B[n/4][n%4+1]);
	if(n/4+1<4)
	fanzhuan1(&B[n/4+1][n%4]);
	if(n/4-1>=0)
	fanzhuan1(&B[n/4-1][n%4]);
	if(n%4-1>=0)
	fanzhuan1(&B[n/4][n%4-1]);
}
void per(int n,int *A,int cur)
{
	int i,j,u,v;
	if(cur==n)
	{
		for(i=0;i<n;i++)
		{
			fanzhuan(A[i]);
		}
		if(finished())
		{
			if(n<min)
			min=n;
		}
	for(u=0;u<4;u++)
	for(v=0;v<4;v++)
	{
		if(str[u][v]=='b')
		B[u][v]=-1;
		else
		B[u][v]=1;
	}
	}
	else for(i=1;i<=16;i++)
	{
		int ok=1;
		for(j=0;j<cur;j++)
			if(A[j]>=i) ok=0;
		if(ok)
		{
			A[cur]=i;
			per(n,A,cur+1);
		}
	}
	
}
int main()
{
	int i,j;
	int A[100];
	int cur;

	for(i=0;i<4;i++)
	{
		gets(str[i]);
	for(j=0;j<4;j++)
	{
		if(str[i][j]=='b')
		B[i][j]=-1;
		else
		B[i][j]=1;
	}
	}
	if(finished())
	{
		printf("0");
	}
	else{
		for(i=1;i<16;i++)
		{
			cur = 0;
			per(i,A,cur);
		}
		if(min==100)
		printf("Impossible");
		else
		printf("%d",min);
	}
	
} 


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