poj 1312棋盤問題（深搜）

• 在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放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

和八皇後類似

#include<iostream>
#include<cstring> 
using namespace std;
int n, k,ans,cnt;
int a[10][10];
bool vis[10];
void dfs(int x,int cnt) {
	if (cnt==k) {
		ans++;
		return;
	}
	if (x > n) return;//别忘了
	for (int i = 1; i <= n; ++i) {
		if (!vis[i] && a[x][i]) {
			vis[i] = true;
			dfs(x + 1,cnt+1);
			vis[i] = false;
		}
	}
	dfs(x + 1,cnt);//如果一行都沒有棋盤位置 則層數加一繼續 計數器不變
}
int main() {
	while (cin >> n >> k) {
		memset(vis,0,sizeof(vis));
		ans=0,cnt=0;
		if (n == -1 && k == -1) return 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				char c;
				cin >> c;
				if (c == '#') a[i][j] = 1;
				else if (c == '.') a[i][j] = 0;
			}
		}
		dfs(1,0);
		cout << ans << endl;
	}
	system("pause");
	return 0;
}
           

補充：

首先題目中的k棋子個數我們可以作為出口條件，隻要放的棋子數等于k就得到一個答案。

然後我們看條件兩個棋子不能放在同一行或者同一列，那我們就可以一行一行地放，每行放一個，就能確定同一行沒有兩個棋子，然後用vis來記錄每一列是否放過棋子。

在考慮每一行放棋子時，别忘了還有該行沒有棋盤放不了棋子的情況。