| ||||||||||
| 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