POJ 1321盤問題深捜+遡及

碁盤問題
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 24958
Accepted: 12333
Description
1つの所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.並べ替え時に任意の2つの駒が碁盤の中の同一行または同一列に置かれないことを要求する場合は、所定の形状と大きさの碁盤に対してk個の駒を並べたすべての実行可能な並べ替えスキームCをプログラミングして解いてください.
Input
複数セットのテストデータを入力します.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
Output
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
Sample Input

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

Sample Output

2
1

深搜+遡及法.
ここでは、1次元配列c,c[i]=jでi行目、j列目の既存を表すN皇后問題を解決する方法を採用する.
また、遡及時にc[]タグを返信することに注意してください.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef __int64 ll;

int vis[10][10],map[10][10],c[10],n,k,tot;
char m[10][10];

//  
void dfs(int cur,int cnt)
{
	int i,j;
	if(cnt==k){		//  k  tot+1
		tot++;return ;
	}
	if(n-cur+1<k-cnt) return ;		//         k      
	if(cur>n) return ;
	int ok=0;
	for(i=1;i<=n;i++) if(map[cur][i]) {ok=1;break;}		//    cur           
	if(ok){
		for(;i<=n;i++){
			int ok2=1;
			if(map[cur][i]){
				for(j=1;j<cur;j++)
					if(c[j]==i){ok2=0;break;}
					if(ok2) {
						c[cur]=i;			//      N     ，c[i]=j     i 、 j 
						dfs(cur+1,cnt+1);
						c[cur]=0;			//    ，   
					}
			}
		}
	}
	dfs(cur+1,cnt);
	return ;
}


int main()
{
	int i,j;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		if(n==-1 && k==-1) break;
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++){
				scanf(" %c",&m[i][j]);
				if(m[i][j]=='#')
					map[i][j]=1;
			}
		memset(c,0,sizeof(c));
		tot=0;
		dfs(1,0);
		printf("%d
",tot);
	}
	return 0;
}