总时间限制: 1000ms 内存限制: 65536kB

描述

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

输入

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

输出

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

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

思路

从第0行出发, 遍历每一列, 当发现棋盘#就标记放一个棋子, 深度搜索下一行.

临界条件: 当行数row等于棋盘行数N时, 方案数自增, 然后返回上一层.

代码

#include <iostream>
#include <cstring>
using namespace std;
int N, K;               // N行N列矩阵, K个棋子
char panel[10][10];     // 棋盘
int placed[10];         // 记录一列是否被放置棋子
int solutionNum;        // 方案数
int alreadyPlace;       // 已放置到棋盘的棋子数
void DFS(int row) {
    if( alreadyPlace == K ) {   // 棋子摆完了, 方案数+1
        solutionNum++;
        return;
    }
    if( row >= N )
        return;
    /* 一列一列去遍历 */
    for(int j = 0; j < N; j++) {
        if( placed[j] == 0 && panel[row][j] == '#' ) {
            placed[j] = 0x1;    // 标记在这放棋子
            alreadyPlace++;
            DFS(row+1);         // 深度搜索下一行
            placed[j] = 0x0;    // 撤销标记
            alreadyPlace--;
        }
    }
    DFS(row+1);     // 深度搜索下一行
}
int main() {
    /* Read data */
    while( cin >> N >> K ) {
        if( N == -1 || K == -1 )
            break;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cin >> panel[i][j];
            }
        }
        /* Initialize data */
        memset(placed, 0x0, sizeof(placed));
        solutionNum = 0;
        alreadyPlace = 0;
        /* DFS and display result */
        DFS(0);
        cout << solutionNum << endl;
    }
    return 0;
}