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 |
DFS 16ms过#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> int n,k; char table[20][20]; int vis[20][20]; int ans; int cnt; bool check(int row,int col) { int i; if(table[row][col]!='#') return false; for(i=0;i<n;i++) if(vis[i][col]==1) return false; return true; } void dfs(int st) { int i,j; if(cnt==k) { ans++; return ; } if(st>=n) return ; for(i=st;i<=n-k+st;i++) { for(j=0;j<n;j++) { if(check(i,j)) { cnt++; vis[i][j]=1; dfs(i+1); vis[i][j]=0; cnt--; } } } } int main() { while(scanf("%d %d",&n,&k)!=EOF) { if(n==-1&&k==-1) break; cnt=0;ans=0; memset(table,0,sizeof(table)); memset(vis,0,sizeof(vis)); int i,j; for(i=0;i<n;i++) scanf("%s",table[i]); dfs(0); printf("%d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator