poj 1321 棋盘问题（回溯法）

棋盘问题

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 69951		Accepted: 33143

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

题目大意：

给你一个不规则的棋盘（棋盘见样例），和定量棋子，问有多少种摆放方式，使得棋盘上每行每列都最多只有一枚棋子。

回溯法的经典题。

类似八皇后。

就是逐行搜索，确定每一行棋子放在哪，找到一个解后返回上一步。

第一次写是参考别人的代码的，用了isok函数，思路比较清晰吧，后来自己优化了一下。

#include <cstdio>

using namespace std;

int n,k;

char board[][];

int total;

int c[];

bool isok(int row)

{

    if(board[row][c[row]]=='.')

        return false;

    for(int i=;i<row;i++)

    {

        if(c[i]==-)

            continue;

        if(c[i]==c[row])

            return false;

    }

    return true;

}

void queen(int row,int num)

{

    if(num==k)

    {

        total++;

        return;

    }

    if(row==n)

        return;

    for(int i=;i<n;i++)

    {

        c[row]=i;

        if(isok(row))

            queen(row+,num+);

    }

    c[row]=-;

    queen(row+,num);

}

int main()

{

    while(scanf("%d%d",&n,&k),n!=-)

    {

        for(int i=;i<n;i++)

            scanf("%s",board[i]);

        total=;

        queen(,);

        printf("%d\n",total);

    }

    return ;

}

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<string>

#include<iostream>

#define ll long long

#define maxn 10000

char board[][];

int n,k;

int cnt;

int vis[];

void queen(int row,int num)

{

    if(num==)

    {

        cnt++;

        return;

    }

    if(row+num->n)

        return;

    for(int i=;i<=n;i++)

    {

        if(board[row][i]=='#'&&!vis[i])

        {

            vis[i]=;

            queen(row+,num-);

            vis[i]=;

        }

    }

    queen(row+,num);

}

int main()

{

    while(scanf("%d%d",&n,&k),n!=-)

    {

        for(int i=;i<=n;i++)

            scanf("%s",board[i]+);

        cnt=;

        memset(vis,,sizeof(vis));

        queen(,k);

        printf("%d\n",cnt);

    }

    return ;

}

巴特西

poj 1321 棋盘问题（回溯法）

最新文章

热门文章

巴特西

poj 1321 棋盘问题 （回溯法）

最新文章

热门文章

poj 1321 棋盘问题（回溯法）