POJ 1321 棋盘问题[DFS]

wywwzjj

发布于 2023-05-09 14:20:41

1890

发布于 2023-05-09 14:20:41

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

这个题非常经典，深搜的回溯，细细品尝，必有所获。每次遇到合适的位置，立即钻进去，转而进入下一个深搜，直到棋子完全拜完，此深搜结束，回到上一个深搜状态，再进行恢复现场，恢复完后先到下一列，下一列可行又继续前面的状态，换列不能解决就换行，直到行数跑完，行数跑完则结束当前深搜，继续改变上一个深搜状态。“第一个”深搜以最后一行作为起点，才真正结束。

#include <cstdio>
using namespace std;

#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b);++i)

char G[10][10];
bool fg[10] = {0};  // 走过为真
int ans = 0, n, k;

void dfs(int cur, int x) {  // cur为已摆的棋子数， x 为行数
    if(cur == k) {
        ans++;
        return;
    }
    rep(i, x, n)
        rep(j, 0, n)
            if(G[i][j] == '#' && !fg[j]) {
                fg[j] = true;
                dfs(cur+1, i+1);  // 下一行继续摆下一个棋子
                fg[j] = false;
            }
}

int main() {
    while(sf("%d%d", &n, &k) == 2 && n != -1 && k != -1) {
        rep(i,0,n) sf("%s",G[i]);
        dfs(0, 0);  // 第一行开始摆
        pf("%d\n", ans); ans = 0;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018/10/28，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs