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