对比分析

1.与n皇后每行都要摆放皇后不同，本题在按行深搜时某一行可以不放棋子，因此增加一步dfs(r + 1)

2.并且此题当摆放棋子数等于k时，即可将方案数+1并返回至上一层

c++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

char g[N][N];
int col[N];
int n, k;
int res;//记录摆放棋子数
int cnt;//记录方案数

void dfs(int r)
{
    if(res == k)
    {
        cnt ++;
        return;
    }

    if(r == n)
        return;

    for(int i = 0; i < n; i ++)
    {
        if(g[r][i] == '#' and !col[i])
        {
            col[i] = 1;
            res ++;
            dfs(r + 1);
            col[i] = 0;//恢复现场
            res --;
        }
    }

    dfs(r + 1);

}

int main()
{
    while(cin >> n >> k, n != -1)
    {
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                cin >> g[i][j];

        res = 0, cnt = 0;

        dfs(0);

        cout << cnt << endl;
    }
}