POJ1321-DFS八皇后变种

Question:

本体是八皇后的变种题目，改为不规则的棋盘，但是还是要求每个妻子不能同行同列 求对于对应的棋盘和妻子个数输出所有的和法的摆放的个数

Solution:

我们这里利用一个小技巧，我们开辟行数组和列数组，用来记录那些行和那些列别占用过 剩下的就是标准的DFS了 这里我第一次T是因为行数加错了，我们下一次直接从上一次的旗子的下一行开始摆放，这样节省时间

Code:

#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cstdio"

using namespace std;

int n,k;
char map[10][10];
int row[10];
int col[10];
int sum;

void init()
{
	memset(map,0,sizeof(map));
	memset(row,0,sizeof(row));
	memset(col,0,sizeof(col));
	sum=0;
}

void dfs(int step,int hang)
{
	if(step==k) 
	{
		sum++;
		return ;
	}
	for(int i=hang+1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(row[i]==1||col[j]==1||map[i][j]!='#') continue;
			else
			{
				row[i]=col[j]=1;
				dfs(step+1,i); 
				row[i]=col[j]=0;
			}
		}
	}
} 

int main()
{
	while(scanf("%d%d",&n,&k)&&(n+k)!=-2)
	{
		init();
		getchar();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				scanf("%c",&map[i][j]);
			}
			getchar();
		}
		dfs(0,0);   //第0步
		cout<<sum<<endl; 
	} 
	return 0;
}