POJ-1321碁盤問題(DFS)

所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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題意分析:所与の碁盤内で、#は駒を置くことができることを表して、すべての#の上で所与の駒の数の下で異なる列の可能な方案の数を求めて、8皇后と少し似ていて、私はDFSを使ってこの過程を実現して、具体的なコードは以下の通りです:

#include
#include
int n,tot,k,book[20];
char str[20][20];
void dfs(int cur,int y)
{
	int i,j;
	if(y==k)
		tot++;
	else
	{
		for(i=cur;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(str[i][j]=='#'&&book[j]==0)
				{
					book[j]=1;//          
					dfs(i+1,y+1);//           ，        
					book[j]=0;
				}
			}
		}
	}
}
int main()
{
	int i,j;
	while(~scanf("%d%d",&n,&k))
	{
		memset(book,0,sizeof(book));
		if(n==-1&&k==-1)
			break;
		tot=0;
		for(i=0;i<n;i++)
		{
	        getchar();
	        for(j=0;j<n;j++)
	        	scanf("%c",&str[i][j]);
        }
		dfs(0,0);
		printf("%d
",tot);
	} 
	return 0;
}