棋盤問題
在一個給定形狀的棋盤(形狀可能是不規則的)上面擺放棋子,棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列,請程式設計求解對于給定形狀和大小的棋盤,擺放k個棋子的所有可行的擺放方案C。
Input
輸入含有多組測試資料。
每組資料的第一行是兩個正整數,n k,用一個空格隔開,表示了将在一個n*n的矩陣内描述棋盤,以及擺放棋子的數目。 n <= 8 , k <= n
當為-1 -1時表示輸入結束。
随後的n行描述了棋盤的形狀:每行有n個字元,其中 # 表示棋盤區域, . 表示空白區域(資料保證不出現多餘的空白行或者空白列)。
Output
對于每一組資料,給出一行輸出,輸出擺放的方案數目C (資料保證C<2^31)。
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
2
1
#include<iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int visit[20];
char mp[20][20];
int ans;//ans表示方案數
int k;//k表示棋子數目
int n;//n表示棋盤的大小
int DFS(int x,int count)
{
if(count==k)//判斷是否棋子已經用完,如果用完,記錄方案數加1,然後直接傳回0
{
ans++;
return 0;
}
for(int i=x;i<n;i++) //可能一行沒有可以放的位置
{
for(int j=0;j<n;j++)
{
if(!visit[j]&&mp[i][j]=='#')
{
visit[j]=true;
DFS(i+1,count+1);//搜尋下一行
visit[j]=false;//回溯
}
}
}
return 0;
}
int main()
{
while(cin>>n>>k)
{
if(n==-1&&k==-1)
break;
memset(visit,false,sizeof(visit));
memset(mp,false,sizeof(mp));
for(int i=0;i<n;i++)
cin>>mp[i];
ans=0;
DFS(0,0);
cout<<ans<<endl;
}
return 0;
}