题目描述

样例

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int N = 10;
int n,k;
char g[N][N];
int vx[N],vy[N],ans;//vx,vy记录每行每列是否被放置过
void dfs(int u,int cnt)
{
    if(cnt == k)//符合情况
    {
        ans++;
        return;
    }
    if(u == n)//枚举到最后n+1行返回
    return;
    for(int i = u;i < n;i++)
    {
        for(int j = 0;j < n;j++)//按列枚举
        {
            if(g[i][j] == '#' && !vx[i] && !vy[j])//在棋盘内，且行和列未放置
            {
                vx[i] = 1;
                vy[j] = 1;
                dfs(i + 1,cnt + 1);//按行枚举
                vx[i] = 0;
                vy[j] = 0;
            }

        }
    }

}
int main()
{
    while(scanf("%d%d", &n, &k) && n != -1 && k != -1)
    {
        memset(vx,0,sizeof(vx));
        memset(vy,0,sizeof(vy));
        ans =  0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> g[i][j];

        dfs(0,0);
        cout << ans << endl;
    }

    return 0;
}