POJ 1321 棋盘问题 深搜+回溯

#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\n",tot);
	}
	return 0;
}