POJ 1321 棋盘问题(DFS简单搜索)

http://poj.org/problem?id=1321

题意是给你一个n * n的矩阵,上面有若干块是可以放置棋子的,问你摆放k个棋子的所有可能性。
这里用DFS求解,从第1行到第n行,每行再去试第1列到第n列,尝试是否能放棋子。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n, k, ans, cnt;
char b[10][10];
bool book[10]; // 用来记录每一列是否放置棋子

void DFS(int cur) {
    if (cnt == k) {
        ans++;
        return;
    }
    if (cur > n)
        return;

    // 遍历当前行的每一列,尝试放棋子
    for (int i = 1; i <= n; ++i) {
        if (!book[i] && b[cur][i] == '#') {
            book[i] = true;
            cnt++;
            DFS(cur + 1);
            book[i] = false;
            cnt--;
        }
    }
    
    DFS(cur + 1); // 到下一行
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(false);

    while (cin >> n >> k && n != -1 && k != -1) {
        fill(book + 1, book + n + 1, false);
        ans = cnt = 0;
        for (int i = 1; i <= n; ++i) {
            getchar();
            for (int j = 1; j <= n; ++j) {
                cin >> b[i][j];
            }
        }
        // DFS从第1行 ~ 第n行
        DFS(1);
        cout << ans << endl;
    }
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容