学步园

也不知道是第几次写这个了,应该掌握了吧????这是一道很经典的DFS题目,

很经典的模版,

DFS:

首先,要有结束条件,

然后要有,搜索条件,就是满足了什么样的条件才会去搜索.

贴出我的代码:

/*
 *N皇后问题
 *是一个很典型的DFS
 *而且也很典型 
 */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

int cnt;//用来记录成立的次数 

int vis[3][55];//0,代表的是列数是否已经被访问,1,表示右斜方向是不是被访问了,2,表示左斜是不是被访问了 

int N;//代表皇后的个数 

void Init()
{
	memset(vis, 0, sizeof(vis));//将vis全部置零 
	cnt = 0;//将统计成立次数置零 
}

void DFS(int cur)
{
	if (cur == N + 1)//如果已经全部访问了一遍且都成功了,次数加1,返回. (结束条件)
	{
		cnt++;
		return ;
	}
	for (int i = 1; i <= N; i++)
	{
		if (!vis[0][i] && !vis[1][cur + i] && !vis[2][i - cur + N])//(搜索条件)
		{
			vis[0][i] = vis[1][cur + i] = vis[2][i - cur + N] = 1;
			DFS(cur + 1);
			vis[0][i] = vis[1][cur + i] = vis[2][i - cur + N] = 0;//这一点很容易犯错,一定要弄清楚是不是回溯的算法. 
		}														  //而这个N皇后问题,确实是一个回溯的算法.	
	} 
}

int main()
{
	while (scanf("%d", &N) != EOF)
	{
		Init();//每次都要进行一次初始化 
		DFS(1);
		printf("%d\n", cnt);
	} 
	system("pause");
	return 0;
}