棋盘问题传送门

POJ - 1321 棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
INPUT
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
OUTPUT
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
SIMPLE INPUT
2 1
#.
.#
4 4
…#
…#.
.#…
#…
-1 -1
SIMPLE OUTPUT
2
1

src="http://cdn.abowman.com/widgets/hamster/hamster.swf" width="300" height="225" scrolling="NO"> 
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
/* v用来记录该列是否有棋子； m用来存图； sum用来记录已放棋子的数量； cnt用来记录方法数量； */
int n, k, v[150],sum = 0, cnt = 0;
char m[150][150];
void dfs(int x)
{
    if(sum == k)// 如果所有的棋子都被放完了则总数加一
    {
        cnt++;
        return;
    }
    if(x > n) // 当行数大于棋盘数时返回上一步；
        return;
    for(int i = 0; i <= n; i++)// 依次遍历每一列寻找可以放棋子的位置
    {
        if(v[i] == 0 && m[x][i] == '#')
        {
            v[i] = 1;
            sum++;
            dfs(x + 1);
            v[i] = 0;
            sum--;
        }
    }
    dfs(x + 1);
}
int main()
{
    while(cin >> n >> k)
    {

        if(n == -1 && k == -1)
            break;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> m[i][j];
            }
        }
        cnt = 0;//初始化很重要
        sum = 0;
        memset(v, 0, sizeof(v));
        dfs(1);
        cout << cnt << endl;
    }
}

在dfs函数中的结尾部分再一次调用了dfs函数，令人费解？那么我们来分析一下dfs 函数是如何运行的首先我们把x = 1 传进dfs中表示从第一行开始搜索，接下来用for循环搜索这一行中的每一列，找到可以放棋子的位置，使用v标记这一列已经被放过棋子，接下来调用dfs（x + 1）继续重复上述步骤搜索，如果搜索不到可以放棋子的位置返回上一步，所以dfs是不能进入这一行的下一行，这样有些情况就考虑不到了，所以在函数末加入一个dfs（x + 1）这样就可以进入这一行的下一行了
原创

简单搜索
举报
收藏
赞