POJ 1312棋盤問題

問題

題目連結

• 在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C

input

• 在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C

Output

• 對于每一組資料，給出一行輸出，輸出擺放的方案數目C （資料保證C<2^31）

Sample Input

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

Sample Output

2
1
           

問題分析

分析連結

AC代碼

#include <iostream>
#include <cstring>
using namespace std;

int n,k;
int sum;
int count; 
int T[8];
char s[10][10];


void dfs(int x,int n,int k){
	if(count == k){
		sum = sum + 1;
		return ;
	}
	
	if(x >= n) {
		return ;
	} 
	
	for(int i = 0; i < n; i++){
		if(!T[i] && s[x][i] == '#'){
			T[i] = 1;
			count++;
			dfs(x+1,n,k);
			T[i] = 0;
			count--;
		}
	}
	dfs(x+1,n,k);
}


int main(){
	while(1){
		cin>>n>>k;
		if(n == -1 && k == -1){
			break;
		}
		
		sum = count = 0;
		
		for(int i = 0; i < n; i++){
			cin>>s[i];
		}
		memset(T, 0 , sizeof(T));
		dfs(0,n,k);		
		cout<<sum<<endl;
	}
}