poj1321 dfs 0ms

#include<cstdio>
#include<cstring>
using namespace std;
bool matrix[10][10];
bool row[10];//行有无
int ans = 0,n,k,cnt = 0;
void dfs(int r)
{
    if(cnt==k){
        ans++;
        return;
    }
    if(r>=n||(cnt+n-r)<k) return;//剪枝直接0ms，未加后面的判断是125ms
    for(int i = 0;i<n;++i)
    {
        if(!row[i]&&matrix[r][i])
        {
            cnt++;
            row[i] = true;
            dfs(r+1);
            cnt--;
            row[i] = false;
        }
    }
    dfs(r+1);//关键，可以不放这一列，直接下一列
    return;
}
int main()
{

    char c;
    while(scanf("%d%d",&n,&k)&&n!=-1)
    {
        ans = 0;
        memset(matrix,0,sizeof(matrix));
        memset(row,0,sizeof(row));
        for(int i = 0; i<n; ++i)
        {
            getchar();
            for(int j = 0; j<n; ++j)
            {
                scanf("%c",&c);
                if(c=='#') matrix[i][j] = true;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}