棋盘问题

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 96005 Accepted: 43758

Description

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

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

1
2
2
1

Source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string>map;
//vector<bool>line;
int cnt;
int ans;
void clear(){
    map.clear();
    cnt=0;
    ans=0;
}
int N;
int K;
void backtrace(int j,vector<bool>&line) {
    if (cnt == K) {//注意出递归的条件是cnt==K也就是找到这么多个
        ans++;
        return;
    }
    if(j>=N){//这里是为了防止遍历的行数超过边界
        return;
    }
        for (int i = 0; i < N; i++){
            if(!line[i]&&map[j][i]=='#'){
                line[i]=true;
                cnt+=1;
                backtrace(j+1,line);
                cnt-=1;
                line[i]=false;
            }
        }
        backtrace(j+1,line);//遍历下一行


}
int main() {
    //std::cout << "Hello, World!" << std::endl;
    //vector<string>map;
    int n;
    int t;
    clear();
    vector<bool>line(9, false);
    while(cin>>n&&cin>>t){
        if(n==-1&&t==-1){
            break;
        }else{
            N=n;
            K=t;
            for(int i=0;i<n;i++){
                string a;
                cin>>a;
                map.push_back(a);
            }
            for(int i=0;i<9;i++){
                line[i]=false;
            }
            backtrace(0,line);
           // N=n;

//            for(int i=0;i<n;i++){
//                for(int j=0;j<n;j++)
//                cout<<map[i][j]<<" ";
//            }

        cout<<ans<<endl;
            //cout结果;
            clear();
        }
    }
    return 0;
}

PS:leetcode刷题表示所有的OJ题