DFS POJ 1321 棋盘问题

题目传送门

 /*
DFS:因为一行或一列都只放一个,可以枚举从哪一行开始放,DFS放棋子,同一列只能有一个
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; char maze[][];
bool vis[];
int n, k, ans; void DFS(int x, int num) {
for (int i=; i<=n; ++i) {
if (maze[x][i] == '#' && !vis[i]) {
if (num == ) ans++;
else {
vis[i] = true;
for (int j=x+; j<=n-num+; ++j) {
DFS (j, num-);
}
vis[i] = false;
}
}
}
} int main(void) { //POJ 1321 棋盘问题
while (scanf ("%d%d", &n, &k) == ) {
if (n == - && k == -) break;
for (int i=; i<=n; ++i) scanf ("%s", maze[i] + );
memset (vis, false, sizeof (vis)); ans = ;
for (int i=; i<=n-k+; ++i) {
DFS (i, k);
}
printf ("%d\n", ans);
} return ;
}
上一篇:PTA 5-3 解题报告


下一篇:python入门14 字典dict