描述
在一個給定形狀的棋盤（形狀可能是不規(guī)則的）上面擺放棋子，棋子沒有區(qū)別赠制。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對于給定形狀和大小的棋盤绽媒，擺放k個棋子的所有可行的擺放方案C浩蓉。
輸入
輸入含有多組測試數(shù)據(jù)誊抛。
每組數(shù)據(jù)的第一行是兩個正整數(shù)入愧，n k涉兽，用一個空格隔開叫胖，表示了將在一個n*n的矩陣內(nèi)描述棋盤草冈，以及擺放棋子的數(shù)目。 n <= 8 , k <= n
當(dāng)為-1 -1時表示輸入結(jié)束瓮增。
隨后的n行描述了棋盤的形狀：每行有n個字符怎棱，其中 # 表示棋盤區(qū)域， . 表示空白區(qū)域（數(shù)據(jù)保證不出現(xiàn)多余的空白行或者空白列）绷跑。
輸出
對于每一組數(shù)據(jù)拳恋，給出一行輸出，輸出擺放的方案數(shù)目C （數(shù)據(jù)保證C<2^31）砸捏。樣例輸入
樣例輸入
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
樣例輸出
2
1
代碼
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int Cal(char **A, int n, int k, int start, bool *rec) {
if (k > n - start) {
return 0;
}
if (k == 0 ) {
return 1;
}
int result = Cal(A, n, k, start+1, rec);
for (int i = 0; i < n; i++) {
if (A[start][i] != '.' && rec[i]) {
rec[i] = false;
result += Cal(A, n, k - 1, start + 1, rec);
rec[i] = true;
}
}
return result;
}
int main() {
//從文件輸入
ifstream cin("C:/Users/97001/Desktop/hw1_6.txt");
string line;
while (getline(cin, line))
{
if (line[0] == '-')
{
break;
}
int n, k;
stringstream ss(line);
ss >> n >> k;
char **A = new char*[n];
bool *rec = new bool[n];
for (int i = 0; i < n; i++) {
getline(cin, line);
A[i] = new char[n];
for (int j = 0; j < n; j++) {
A[i][j] = line[j];
}
rec[i] = true;
}
cout << Cal(A, n, k, 0, rec) << endl;
}
getchar();
}
