题目地址:http://poj.org/problem?id=1321

题目描述

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

思路

这也是一道搜索题,采用DFS遍历搜索。

AC代码

/*************************************************************************
    > File Name: 6250_B.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sun 03 May 2015 20:47:50 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

char board[10][10]; // 棋盘布局
bool col[10]; // 保存列存放棋子状态
int ans=0; // 方案数量
int num=0; // 当前已放棋子数量
int n,k; // 棋盘大小,棋子数量
void DFS(int i) {
    if(num == k)  { // 得到一个解
        ++ans;
        return;
    }
    if(i>=n) // 回溯
        return;
    for(int j=0; j<n; ++j) { // 按列遍历
        if(!col[j] && board[i][j] == '#') { // 可放棋子
            col[j] = true; //在第i行该列放置棋子
            ++num; // 放置棋子数量+1
            DFS(i+1); // 下一行i+1搜索
            col[j] = false; // 搜索完毕,当前第i行该列取出棋子
            --num; // 放置棋子数量-1
        }
    }
    DFS(i+1); // 下一行搜索
}

int main()
{
    while(scanf("%d%d", &n, &k)==2 && !(n==-1&&k==-1)) {
        getchar();
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j)
                board[i][j] = getchar();
            getchar();
        }
        memset(col, 0, sizeof(col));
        num = ans = 0;
        DFS(0);
        printf("%d\n", ans);
    }
    return 0;
}