(最近在做kuangbin帶你飛專題)問題鏈接：棋盤問題
這是一道入門dfs的題目，以為n的比較小，所以完全可以用dfs的方法通過這一道題。
我們先討論一下這一道題目的思路，要求棋子的橫豎均只能有一個棋子，我們可以對行進(jìn)行dfs，用一個記錄數(shù)組表示列是否已經(jīng)含有棋子，既1表示有，0表示沒有。dfs的過程中，填充棋子的數(shù)量等于k時，此dfs結(jié)束cnt++返回上一層，若遍歷的行號等于n既已出范圍直接結(jié)束此層dfs。若本行可填，注意回溯。
另外要注意k的大小會比n要小，dfs的情況需要注意。
ac代碼如下：

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
int k, n, cnt;
char s[10][10];
int col[10];
void dfs(int x, int num)
{
    if(num==k)
    {
        cnt++;
        return;
    }
    if(x==n)return;
    for(int i=0; i<n; i++)
        {
        if(s[x][i]=='#'&&!col[i])
        {
            col[i]=1;
            dfs(x+1, num+1);
            col[i]=0;
        }
    }
    if(x<n)
    dfs(x+1, num);
}

int main(void)
{
    while(scanf("%d%d", &n, &k))
    {
        cnt=0;
        memset(col, 0, sizeof(col));
        if(k==-1&&n==-1)
        break;
        for(int i=0; i<n; i++)
        scanf("%s", s[i]);
        dfs(0, 0);
        printf("%d\n", cnt);
    }
    return 0;
}

over