| ||||||||||
| 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 | |||||||||
TLE!!AAAAAAAAA居然TLE了!!!!!!!!!求教育#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator