深度搜索(DFS)，一种用于遍历和搜索的算法「终于解决」

大家好，欢迎来到IT知识分享网。

先上百度对深度搜索的定义：

 如果上边的定义没有理解，那么可以这样认为：深度搜索就是一种试探性的算法，例如你在一个十字路口想要去到某地，但是你又不认识具体的路(并且你不善言辞，万事不求人)，那么你只能先选一个方向走，一直走下去直到发现此路不通，这时你又会掉头回到起始的十字路口，在往另一个方向试试，直到找到你要去的那个地方。

这个不断试探的方式，套用的是递归的基本思想，大体DFS结构如下：

void dfs(控制参数)
{
    边界判断(递归出口)
    {
        到达边界时的操作
    }
    未到边界时尝试每一种可能else
    {
        满足条件 if
        {
            标记
            继续下一步 : dfs(step+1)（递归）
            恢复初始状态，回溯
        }
    };
}

应用

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1 ≤ n ≤ 7 1≤n≤71≤n≤7
输入样例：
3
输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 public class DFS
    {
        //设定一个存储的最大值
        const int N = 100;
        //存储路径值
        static int [] arr=new int[N];
        //用于标识当前点是否走过
        static int[]book =new int[N+1];
        /// <summary>
        /// 深度搜索
        /// </summary>
        /// <param name="step">起始点</param>
        /// <param name="sizenum">截止点</param>
        public void dfs(int step, int sizenum)
        {
            //判断边界，已经到达边界则退出
            if (step == sizenum + 1)
            {
                for (int i=1;i<=sizenum;i++)
                {
                    Console.Write(arr[i]+ ",");
                }
                Console.WriteLine();
                return;
            }
            for(int i=1; i<=sizenum; i++)
            {
                //判断当前点是否未走过
                if(book[i] == 0)
                {
                    //加入记录
                    arr[step] = i;
                    //标识当前点已经走过
                    book[i] = 1;
                    dfs(step+1, sizenum);
                    //回溯,取消当前点的标记
                    book[i] = 0;
                }
            }
        }
    }

//调用
DFS d=new DFS();
d.dfs(1, 3);
Console.ReadLine();

N-皇后问题

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。注意：行末不能有多余空格。输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1 ≤ n ≤ 9 1≤n≤91≤n≤9
输入样例：

4

输出样式：

.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..

参考其他博主的解题思路，是通过对角线和反对角线判断点与点之间是否处于同一斜线上，在通过一个数组标记是否在同一列，而行是作为控制参数

深度搜索(DFS) 和 广度搜索(BFS)

条条大陆通罗马，参考了其他博主的解题思路，得出一种不同的解法，思路如下：

假设一个点A 的坐标是[ a , b ] ，那么和该点在同一斜线上的点A′ 有四种,分别是
[a+x,b+x]、[a−x,b−x]、[a+x,b−x]、[a−x,b+x]。
前两种点横纵坐标相减和A点横纵坐标相减后一样。后两种点横纵坐标相加和A点横纵坐标相加一样。

(a+x)−(b+x)=a−b

(a−x)−(b−x)=a−b

(a+x)+(b−x)=a+b

(a−x)+(b+x)=a+b

因此，根据这个我们就可以很方便的判断两个点知否在同一斜线上。只要两个点横纵坐标相加结果相等或者相减结果相等，就可以判断两个点在同一斜线上。
 

原文：八皇后问题–判断是否是在同一斜线上

int n = 4;
//记录每一列是否已经放至一个皇后
int[] col = new int[n];
//图
char[][] map =
{
    new char[] { '.', '.', '.', '.' },
    new char[] { '.', '.', '.', '.' },
    new char[] { '.', '.', '.', '.' },
    new char[] { '.', '.', '.', '.' },

};

//记录上一点的坐标值
int x1 = 0;
int y1 = 0;
DFs(0, x1, y1);

//P:控制当前位于第几行
void DFs(int p,int x,int y)
{
    if(p == n)
    {
        Console.WriteLine("------------------");
        //输出结果
        for(int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Console.Write(map[i][j]);
            }
            Console.WriteLine();
        }
        Console.WriteLine("------------------");
        return;
    }
    //此处控制的是第几列
    for(int i = 0;i <n; i++)
    {
        //判断该列是否还没放至过皇后
        //判断当前点的位置是否与上一个点的位置在同一斜线上
        if (col[i] == 0&&p+i!=x+y&&p-i!=x-y)
        {
            //将该点放至皇后
            map[p][i] = 'q';
            //记录该列已经存在皇后
            col[i] = 1;
            //递归
            DFs(p+1,p,i);
            //回溯
            map[p][i] = '.';
            col[i] = 0;
        }
    }
}