基础算法——深度优先搜索

深搜这个算法相信大家肯定都不陌生吧，它是算法中基础中的基础，它运用到的就是递归了，它还隐式的包含了一种数据结构——栈，我在理解这个算法的时候可吃了不少苦头，花了不少时间，但是一旦掌握，你的思维可以说会提升一个档次，下面让我们一起来看看什么是深搜算法。

算法例题：要说涉及到深搜的问题，不得不说一个名字——n皇后问题,其中n皇后问题中最出名的就是把皇后了，下面我们看看这题目是怎么样的。

在nXn格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法.

 

 

 

 首 先来看这张图片：这是n==8时候的一种情况,但是这只是其中的一种情况，我们要怎么输出所有的情况呢，如果用一般的数组来写的话显然不可能，顶多只能找 到所有解中的某几组，我们试试深搜，当找到其中的一组解之后，使程序在尝试搜索下一组解，直至所有的解都搜索完毕，咦？好像可以做到的样子，行，那我们来 试试吧。

 

 

 

#include<iostream>
#include<math.h>
using namespace std;
int a[8][8],b[8];//a数组表示棋盘最大为8*8,b数组用来表示列,如要表示第i行的列就表示为b[i]
int n,sum;
bool check(int n)
{
	for(int i=0;i<n;i++)
	{

		//b[i]==b[n]来判断是否同一列,abs(i-n)==abs(b[i]-b[n])来判断是否同一对角线

		//这个判断对角线的方法读者稍微想一下就能明白
		if(b[i]==b[n]||abs(i-n)==abs(b[i]-b[n]))
			return 0;
	}
	return 1;
}
void dfs(int x)
{
	for(int i=0;i<n;i++)
	{
		b[x]=i;//(x,b[x])
		if(check(x))//来判断是否跟已经放好在同一列，或是同一个对角线上
		{
			if(x==n-1)//若棋子已经放到第n行了，则说明已经出现一种情况了，则sum+1
			{
				sum++;

				//下面这段打注释的代码是输出每种情况时棋盘状态，读者可先删除
				/*a[x][b[x]]=1;
				for(int p=0;p<n;p++)
                		{
                    			for(int q=0;q<n;q++)
                    			{
                        			cout<<a[p][q]<<" ";
                    			}
                    		cout<<endl;
                		}
                		cout<<endl;
				a[x][b[x]]=0;*/

				return;//返回寻找下一种情况
			}
			else
			{
				a[x][b[x]]=1;//放上棋子
				dfs(x+1);//x还没放到第n行则继续放
				a[x][b[x]]=0;//将原来已放的棋子拿掉
			}
		}
	}
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		sum=0;
		dfs(0);//从第0行开始搜
		cout<<sum<<endl;
	}

return 0;

}