(最近在做kuangbin帶你飛專題)問(wèn)題鏈接：棋盤問(wèn)題
這是一道入門dfs的題目宏娄，以為n的比較小毫玖，所以完全可以用dfs的方法通過(guò)這一道題炼蹦。
我們先討論一下這一道題目的思路羡宙，要求棋子的橫豎均只能有一個(gè)棋子，我們可以對(duì)行進(jìn)行dfs掐隐，用一個(gè)記錄數(shù)組表示列是否已經(jīng)含有棋子狗热，既1表示有钞馁，0表示沒(méi)有。dfs的過(guò)程中匿刮，填充棋子的數(shù)量等于k時(shí)僧凰，此dfs結(jié)束cnt++返回上一層，若遍歷的行號(hào)等于n既已出范圍直接結(jié)束此層dfs熟丸。若本行可填训措，注意回溯。
另外要注意k的大小會(huì)比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
