POJ 1321 棋盘问题

题目链接：POJ 1321 棋盘问题

题目大意：
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放(k)个棋子的所有可行的摆放方案(C)。

题解：
典型DFS题，注意标记每一列的情况和回溯。

#include <iostream>
using namespace std;

int f[10], n, k, ans;
char loc[10][10];

void dfs(int step, int x) {
	if (x > k) {
		return;
	}
	if (step > n) {
		if (x == k) {
			ans++;
		}
		return;
	}
	for (int i = 1; i <= n; ++i) {
		if (loc[step][i] == '#' && f[i] == false) {
			f[i] = true;
			dfs(step + 1, x + 1);
			f[i] = false;
		}
	}
	dfs(step + 1, x);
}

int main() {
	while (cin >> n >> k) {
		if (n == -1 && k == -1) {
			break;
		}
		ans = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				cin >> loc[i][j];
			}
		}
		dfs(1, 0);
		cout << ans << endl;
	}
	return 0;
}