在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有區別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C。

Input

輸入含有多組測試數據。?
每組數據的第一行是兩個正整數，n k，用一個空格隔開，表示了將在一個n*n的矩陣內描述棋盤，以及擺放棋子的數目。 n <= 8 , k <= n?
當為-1 -1時表示輸入結束。?
隨后的n行描述了棋盤的形狀：每行有n個字符，其中 # 表示棋盤區域， . 表示空白區域（數據保證不出現多余的空白行或者空白列）。?

Output

對于每一組數據，給出一行輸出，輸出擺放的方案數目C （數據保證C<2^31）。

Sample Input

2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1

Sample Output

2 1

這個題就是一個簡化版的N皇后問題，問的是有哪些情況，所以深搜，題意是說給你N*N的棋盤，有的的地方能放，而且不能在一條水平線和豎直線上。

#include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0);//?D2??éó?scnaf￡? #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b using namespace std; typedef long long ll; const int N = 10; int n,k; int flag[N]; char a[N][N]; queue<int>q; int cnt,ans; void dfs(int x) {if(x==n+1) return ;for(int i=1;i<=n;i++){if(a[x][i-1]=='#'&&flag[i]==0){flag[i]=1;cnt++;if(cnt==k) ans++;dfs(x+1);cnt--;flag[i]=0;}}dfs(x+1); }int main() {while(cin>>n>>k){cnt=0;ans=0;if(n==-1||k==-1)break;for(int i=1;i<=n;i++){cin>>a[i];}/* for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}*/dfs(1);cout<<ans<<endl;}}

?

總結

以上是生活随笔為你收集整理的POJ - 1321 棋盘问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。