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 |
最后加一条 = 260ms -> 250ms 收工In Reply To:加一条 = 500ms -> 260ms Posted by:wcfairytale at 2011-10-10 01:24:09 #include<stdio.h> #include<string.h> int map[17][301]; int rn[17]; int cn[301]; bool is_useful[17]; bool flag; int M,N; int i,j; int tn[301]; int rest[17]; int is_rest_has[17][301]; void dfs(int depth, int total) { if(flag)return;//has found if(total == N) //found!! { flag = true; return; } if(depth == M)return; if(total + rest[depth] < N)return;//not enough 1 for(i=0;i<N;i++) { if(tn[i] == 0 && is_rest_has[depth][i] == 0)return; //rest rows, no 1 on coli if(tn[i] !=0 && map[depth][i] !=0)//more than one 1 { dfs(depth+1,total); return; } } if(!is_useful[depth]) //rn[depth] = 0 { dfs(depth+1,total); return; } if(total + rn[depth] > N)//not ok { dfs(depth+1,total); return; } //dont use the row dfs(depth+1,total); if(flag)return;//has found //use the row for(i=0;i<N;i++) tn[i] += map[depth][i]; dfs(depth+1,total+rn[depth]); for(i=0;i<N;i++) tn[i] -= map[depth][i]; } int main() { int i,j; while(scanf("%d%d",&M,&N) != EOF) { for(i=0;i<M;i++) { rn[i]=0; is_useful[i]=true; } for(i=0;i<N;i++) { cn[i]=0; tn[i]=0; } flag = false; for(i=0;i<M;i++) for(j=0;j<N;j++) { scanf("%d",&map[i][j]); is_rest_has[i][j]=0; if(map[i][j]!=0) { rn[i]++; cn[j]++; } } for(i=0;i<N;i++)is_rest_has[M-1][i]=map[M-1][i]; for(i=M-2;i>=0;i--) { for(j=0;j<N;j++) { if(is_rest_has[i+1][j] || map[i][j]) is_rest_has[i][j] = 1; } } rest[M-1] = rn[M-1]; for(i=M-2;i>=0;i--) rest[i] = rest[i+1]+rn[i]; //if a rown == 0 then the row is useless for(i=0;i<M;i++) if(rn[i]==0)is_useful[i]=false; //if a coln == 0 then impossible for(i=0;i<N;i++)if(cn[i]==0)break; if(i!=N) { printf("It is impossible\n"); continue; } dfs(0,0); if(flag) printf("Yes, I found it\n"); else printf("It is impossible\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator