棋盘问题 poj 1321

题目：

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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

思路分析：这是一道dfs的搜索题。其搜索关键在于如何搜索，以及搜索中的限定条件是什么。如果像普通的二维数组一样一个一个的搜索，那么限定条件会是相当的麻烦，甚至根本不知如何去限定，但是如果是按行搜索，那么我们只需要判断每一行的列。

//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int MAXN = 8+2;

int n, k;
char str[MAXN][MAXN];
int vis[MAXN];      // 按行搜索，所以只需要一位的标记数组，标记列

int d[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
int ans = 0;

void DFS( int x, int cnt )
{
    if( cnt == k )
    {
         ans ++;
         return ;  // 满足条件就可以删除当前的状态，因为再往下也不会有符合的状态了
    }

    for( int i=x; i<n; i++ )     // 按行搜索
    {
        for( int j=0; j<n; j++ )
        {
            if( str[i][j] == '#' && vis[j] != 1 )    // vis[j] 标记的是列，因为按行搜索不可能出现两个在同一行
            {
                vis[j] = true;
                DFS(i+1, cnt+1);     // 每次递归都在原有的状态基础上增加了一个基于原有基础的状态节点
                                    // 所以不用考虑跳过某一行的问题，每遍历一行产生的新的状态数都是原有的
                                    // 可以单独存在的状态数乘上当前行的节点数
                vis[j] = false;     // 回溯，方便另一个状态的搜索
            }
        }
    }

}


int main()
{
    while( scanf("%d %d", &n, &k ), ( n != -1 || k != -1 ) )    // 都为-1的逆否是只要有一个不为-1
    {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        for( int i=0; i<n; i++ )
            scanf("%s", str[i] );
        DFS(0,0);
        printf("%d\n", ans );

    }




    return 0;
}