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成鬼了,想不通啊,为什么会超时

Posted by love_zhaoqiang at 2012-03-31 19:45:03 on Problem 2965
#include<stdio.h>
char map[4][4];
int dig[4][4];
int B[16],C[16];
int min=17;
int cut=0;
int Judge()
{
	int i,j;
	int a=0,count=0;
	for(i=0;i<16;i++)
	{
		if(B[i]==1)
		{
			for(j=0;j<4;j++)
			{
				dig[i/4][j]=!dig[i/4][j];
				dig[j][i%4]=!dig[j][i%4];
			}
			dig[i/4][i%4]=!dig[i/4][i%4];
			count++;
		}
	}
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			if(dig[i][j]==1)
				a++;
		}
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			if(map[i][j]=='+')
				dig[i][j]=0;
			else
				dig[i][j]=1;
		}
	if(a==16)
		return count;
	else
		return 17;
}

void Subset(int n)
{
	int a,i;
	if(n==16)
	{
		a=Judge();
		if(a<min)
		{
			for(i=0;i<16;i++)
				C[i]=B[i];
			min=a;
		}
		return ;
	}
	B[n]=0;
	Subset(n+1);
	if(cut>=min)
		return;
	B[n]=1;
	cut++;
	Subset(n+1);
	cut--;

}


int main()
{
	freopen("input.txt","r",stdin);
	int i,j;
	for(i=0;i<4;i++)
		scanf("%s",map[i]);
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			if(map[i][j]=='+')
				dig[i][j]=0;
			else
				dig[i][j]=1;
		}
	Subset(0);
	printf("%d\n",min);
	for(i=0;i<16;i++)
		if(C[i]==1)
			printf("%d %d\n",i/4+1,i%4+1);
	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