POJ 1321 棋盘问题 解题报告

一、问题描述

Description

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

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1

#.

.#

4 4

...#

..#.

.#..

#...

-1 -1

Sample Output

2

1

 

二、解题思路

使用回溯法求解。首先将棋盘的所有空白区坐标放在一个数组p中，问题等同于在p个中选择k个位置放棋子，当然同行同列不能有多于2个。row[]和col[]分别表示该行或该列是否已经放过棋子。对于每个位置有放与不放两个选择，解空间是一棵满二叉树，深度为N（N为空白区的个数），当放满k个时，计数器c+=1。

三、代码

 

#include<iostream>
using namespace std;
struct Pos
{
    int x;
    int y;
};
Pos p[81];//空白棋子的位置
int N;

int k;
int n;
bool col[9];
bool row[9];
int c=0;
void backtrace(int n,int j)
{
    int i;
    if(n>=k)
    {
        c++;
        return ;
    }
    for(i=j;i<N;++i)
    {
        int x=p[i].x;
        int y=p[i].y;
        if(row[x] && col[y] )
        {
            row[x]=false;
            col[y]=false;
            backtrace(n+1,i+1);
            row[x]=true;
            col[y]=true;
        }
    }
}
int main()
{
    int i,j;
    char ch;
    while(cin>>n>>k)
    {
        if(n==-1 && k==-1)
            break;
        N=0;
        c=0;
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=n;++j)
            {
                cin>>ch;
                if(ch=='#')
                {
                    p[N].x=i;
                    p[N].y=j;
                    row[i]=true;
                    col[j]=true;
                    N++;
                }
            }
        }
        backtrace(0,0);
        cout<<c<<endl;
    }
    return 0;
}