DFS（深度优先遍历、N皇后问题、2N皇后问题）

目录

一、回溯法与深度优先搜索（DFS）

1. 回溯法：

• 是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯法会通过在上一步进行一些变化来摆脱当前不正确的解，重新尝试其他的可能性。
• 它通常用于解决决策问题，如排列、组合、子集等。
• 回溯法可以隐式地处理图或树，即这些结构并不需要事先构建出来，而是在搜索过程中动态生成。

2. 深度优先搜索（DFS）：

• 是一种用于遍历或搜索树或图的算法。在树中，这种算法搜索最深的节点，而在图中，它将回溯到未探索过的路径。
• DFS从根（或在图中的某个任意节点）开始，探索尽可能深的分支，直到达到目标节点，或者当前分支没有更多的节点可以访问。然后，搜索回溯到开始探索的路径上的下一个节点。
• DFS通常使用栈或递归来实现，其中递归实现更为常见和直观。

关系：

• 回溯法通常使用DFS作为其基本的搜索策略。在回溯法中，DFS用于系统地遍历所有可能的解空间。
• 当我们说“一条路走到黑”时，我们实际上是在描述DFS的特性，即尽可能深入地搜索图的分支，直到达到叶节点或无法继续为止。

• 在排列型问题中，DFS用于生成所有可能的排列，而在子集型问题中，它用于生成所有可能的子集。

尽管在很多情况下回溯法和DFS是紧密相关的，但它们并不总是等价的。回溯法更侧重于问题的求解策略，而DFS更侧重于图的遍历策略。然而，在实际应用中，这两个概念经常交织在一起。

二、DFS与二叉树的前序遍历

2.1、二叉树的前序遍历

前序遍历的步骤如下：

// 先序遍历二叉树  
void PrevOrder(BTNode* root)
{
	// 如果当前节点为空，则打印"NULL"并返回  
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	// 访问当前节点的数据  
	printf("%c ", root->data);
	// 递归遍历左子树  
	PrevOrder(root->left);
	// 递归遍历右子树  
	PrevOrder(root->right);
}

2.2、DFS

基本模型：

void dfs(int step){
	判断边界
	枚举每一种可能 for(i=1;i<=n;i++){
		继续下一步 dfs(step+1)
		}
}

全排列

题目：

输入一个数n，将数字1~n排成一排，按字典序输出所有排列方法。

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int ans[N]; 
bool mark[N];// 标记是否走过
int n;

void dfs(int u) // u代表目前dfs深度
{
	if (u == n)// 判断边界， 找到解
	{
		for (int i = 0; i < n; i++)
			cout << ans[i] << " ";
			// 打印当前排列
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++)// 枚举下一种情况
	{
		if (mark[i] == false)
		// 尝试将每个未使用的数字放入当前位置
		{
			mark[i] = true;// 标记已用
			ans[u] = i;// 数字i放入当前深度u的位置
			dfs(u + 1);// 递归调用dfs函数，处理下一个深度
			mark[i] = false;
			ans[u] = 0;
		}
	}
}

int main()
{
	cin >> n;dfs(0);//从0开始调用dfs函数生成排列
	return 0;
}

这是一个排列型搜索树，实际上的回溯法比较灵活，需要根据题意要求来具体分析。vis[i]表示数字i是否使用过，也经常被用于表示某个元素是否使用过al]存放结果，当dep深度=n+1时说明n层都已经算完了，直接输出结果。子集型搜索树模板结构类似，就是在往下走的时候只有两条边，表示“选或不选当前这个元素”

 2.3、分析

二叉树的前序遍历确实与深度优先遍历（DFS）在原理上是相似的。前序遍历是二叉树深度优先遍历的一种形式。

• 前序遍历顺序：在二叉树的前序遍历中，我们首先访问当前节点（根节点或任意子树的根），然后递归地前序遍历左子树，最后递归地前序遍历右子树。这个“根-左-右”的顺序确保了遍历是深度优先的。
• 深度优先遍历：深度优先遍历是一种树或图遍历算法，它从根节点（或任意节点）开始，尽可能深地探索图的分支。在树中，这意味着沿着树的最深路径进行搜索，直到到达叶节点或无法再深入，然后回溯到开始搜索的路径上的下一个节点。

在二叉树的前序遍历中，每个节点被访问的顺序实际上反映了DFS搜索树的方式。先访问当前节点对应于DFS中的“探索当前节点”，然后深入左子树对应于“先探索最左边的分支”，最后访问右子树则是“在左侧无更多可探索路径时，回溯并探索右侧的分支”。

因此，我们可以说，二叉树的前序遍历是一种特殊形式的深度优先遍历，其中特定的节点访问顺序（根-左-右）体现了DFS的基本原则。两者都是基于深度优先搜索的概念来遍历结构的。

三、N皇后问题

题目描述：

在一个 N x N 的方格棋盘上放置 N 个皇后，要求它们互不攻击，即任意两个皇后不允许处在同一行、同一列，也不允许处在与棋盘边框成 45 度角的斜线上。给定一个正整数 N（N < 10），你的任务是求出在这样的棋盘上放置 N 个皇后的合法方法有多少种。

输入描述：

输入包含一个正整数 N（N <= 10），表示棋盘的大小和需要放置的皇后的数量。

输出描述：

输出一个正整数，表示在给定大小的棋盘上放置 N 个皇后的合法方法数量。

输入：5     

输出：10

朴素解法：

思路：对于这种题，首先，我们想到的是使用二维数组存，然后暴力枚举，判断函数来一个一个判断。那么，就得到了一个大概的思路：对二维数组的所有情况进行枚举，然后对每种情况进行判断，这是这种题目的普遍思想，接下来是对题目进行细致的分析。

这种题主要的难点是判断、遍历如何实现。由题意可知，一行，一列中最多有一个皇后存在，所以可以把一行或一列看成一组，这里我们把一行看成一组。因为第一行是没有放过任何皇后的，所以第一行全部都枚举放置皇后，接下来的每行，我们可以设置一个check函数来检查是否可以放置皇后，这时，就构成了我们代码的完整思路。

思路：

判断皇后是否会相互攻击

• 使用 check 函数来判断在棋盘上某一位置 (deep, m) 放置一个皇后是否合法。deep 代表当前的行号，m 代表列号。
• check 函数的逻辑包括：
  • 检查当前列 m 上是否已经放置了皇后。
  • 检查当前位置的左上方、上方、右上方是否已经放置了皇后。由于是从上到下逐行放置皇后，所以只需要检查上方和左右上方即可，下方还未放置皇后不需要检查。

bool check(int deep, int m) {
    for (int k = 0; k < n; ++k) {
        if (a[k][m]) return false;
        // 检查第 m 列是否有皇后
    }
    // 检查所有方向以判断皇后是否会攻击
    //下方还没有放置皇后，所以不用检查
    for (int i = 1; i <= deep; i++) {
        if (a[deep - i][m]) return false; // 检查上方
        if (m - i >= 0 && a[deep - i][m - i]) return false; // 检查左上方
        if (m + i < n && a[deep - i][m + i]) return false; // 检查右上方
    }
    return true;
}

深度优先搜索与回溯

• 使用 dfs 函数进行深度优先搜索。该函数的参数 deep 表示当前正在尝试放置皇后的行号。
• 若 deep 等于 n，意味着已成功在前 n 行每行都放置了一个皇后并且没有冲突，此时找到了一个合法解，ans 计数器加一。
• 对于每一行，程序尝试在所有列上放置皇后（即遍历每一列），使用 check 函数检查放置是否合法：
  • 如果合法，则在该位置放置皇后（将 a[deep][i] 设为 1），并递归调用 dfs(deep + 1) 尝试在下一行放置皇后。
  • 完成对下一行的探索后（不管是找到解还是回溯），需要将当前位置的皇后移除（回溯），即将 a[deep][i] 设回 0，以便尝试在当前行的其他列上放置皇后。

void dfs(int deep) {
    if (deep == n) {
        ans++;// 找到一个解，解的数量加一
        return;
    }
    for (int i = 0; i < n; ++i) {
    // 尝试在当前行的每一列放置皇后
        if (check(deep, i)) {
            a[deep][i] = 1; // 放置皇后
            dfs(deep + 1);// 递归搜索下一行
            a[deep][i] = 0; // 回溯，移除皇后
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int a[11][11]; 
// 存储棋盘的数组，1表示为皇后，0表示为空 
    int ans = 0; int n;
// 解的数量， 棋盘的大小，即N

// 判断是否有攻击
bool check(int deep, int m) {
    for (int k = 0; k < n; ++k) {
        if (a[k][m]) return false;
        // 检查第 m 列是否有皇后
    }
    // 检查所有方向以判断皇后是否会攻击
    //下方还没有放置皇后，所以不用检查
    for (int i = 1; i <= deep; i++) {
        if (a[deep - i][m]) return false; // 检查上方
        if (m - i >= 0 && a[deep - i][m - i]) return false; // 检查左上方
        if (m + i < n && a[deep - i][m + i]) return false; // 检查右上方
    }
    return true;
}
void dfs(int deep) {
    if (deep == n) {
        ans++;// 找到一个解，解的数量加一
        return;
    }
    for (int i = 0; i < n; ++i) {
    // 尝试在当前行的每一列放置皇后
        if (check(deep, i)) {
            a[deep][i] = 1; // 放置皇后
            dfs(deep + 1);// 递归搜索下一行
            a[deep][i] = 0; // 回溯，移除皇后
        }
    }
}
int main() {
    cin >> n;dfs(0);// 从第0行开始深度优先搜索
    cout << ans;
    return 0;
}

位运算解法：

• row：当前处理的行号。
• col：一个整数，其二进制中的每一位代表棋盘上对应的列，如果某一位是1，表示该列已经放置了皇后。
• pie：一个整数，其二进制表示中的1表示相应的左下到右上的斜线已有皇后。每一位的变化通过左移实现，因为随着行的增加，对角线的覆盖范围向左移动。
• na：一个整数，其二进制表示中的1表示相应的左上到右下的斜线已有皇后。每一位的变化通过右移实现，因为随着行的增加，对角线的覆盖范围向右移动。
• n：棋盘的大小，即皇后的数量。

void dfs(int row, int col, int pie, int na, int n) {
    ...
}

dfs：

在N皇后问题中，位运算的引入是为了高效地处理皇后之间的冲突检测。通过将列(col)、两个方向的对角线(pie, na)用位来表示，可以利用位运算快速检测冲突和更新状态。具体如下：

利用位运算，可以快速找到当前行中所有可放置皇后的位置：

• int bits = (~(col | pie | na)) & ((1 << n) - 1);

计算当前层可放置皇后的位置：

• int bits = (~(col | pie | na)) & ((1 << n) – 1);

通过以上位运算，我们得到了一个整数bits，其每个为1的位都代表当前行一个可尝试放置皇后的位置。

while循环：

• 使用while (bits > 0)循环尝试所有可能的位置。
• int p = bits & -bits;通过取反加一得到最低位的1，即当前尝试的位置。

dfs(row + 1, col | p, (pie | p) << 1, (na | p) >> 1, n);

• 递归调用dfs尝试在下一行放置皇后，同时更新col、pie、na。
• 使用bits &= bits - 1;去除已尝试的位置，准备尝试下一个可能的位置

dfs初始化：

dfs(0, 0, 0, 0, n);的调用表示从棋盘的第一行开始尝试放置皇后，同时初始状态下棋盘是完全空的，没有任何的列或对角线被占用。这是解决N皇后问题的起始点。

#include <iostream>
using namespace std;

int ans = 0;
int n = 0;

void dfs(int row, int col, int pie, int na, int n) {
    if (row >= n) {
        ans++;
        return;
    }
    // 计算当前层可放置皇后的位置
    int bits = (~(col | pie | na)) & ((1 << n) - 1);
    while (bits > 0) {
        int p = bits & -bits; // 取最低位的1
        // 递归到下一行
        dfs(row + 1, col | p, (pie | p) << 1, (na | p) >> 1, n);
        bits &= bits - 1; // 清除最低位的1
    }
}

int totalNQueens(int n) {
    if (n < 1) return 0;
    dfs(0, 0, 0, 0, n);
    return ans;
}

int main() {
    cin >> n;
    cout << totalNQueens(n);
    return 0;
}

四、2N皇后问题

问题描述

　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式

　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式

　　输出一个整数，表示总共有多少种放法。

样例输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

2

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

0

此题为N皇后问题的进阶版，相较于N皇后问题需多考虑一组棋子，并且要考虑是否能放入。我们可以先放入黑皇后，再放入白皇后的思路去实现代码。此时要建立dfsblack和dfswhite两个函数。

#include<bits/stdc++.h>
using namespace std;
int a[10][10],
b[10][10],// 存储黑皇后的位置
c[10][10];// 存储白皇后的位置
bool vis[10][10];
int n;// 棋盘大小
int ans;// 几种方法

// 判断是否有攻击
bool checkblack(int deep, int m) {
    // 检查所有方向以判断皇后是否会攻击
    //下方还没有放置皇后，所以不用检查
    for (int i = 0; i <= deep; i++) {
        if (b[deep - i][m]) return false; // 检查上方
        if (m - i >= 0 && b[deep - i][m - i]) return false; // 检查左上方
        if (m + i < n && b[deep - i][m + i]) return false; // 检查右上方
    }
    return true;
}

bool checkwhite(int deep, int m) {
    // 检查所有方向以判断皇后是否会攻击
    //下方还没有放置皇后，所以不用检查
    for (int i = 0; i <= deep; i++) {
        if (c[deep - i][m]) return false; // 检查上方
        if (m - i >= 0 && c[deep - i][m - i]) return false; // 检查左上方
        if (m + i < n && c[deep - i][m + i]) return false; // 检查右上方
    }
    return true;
}

dfsblack

放完黑皇后的终止条件为：

if (deep == n) {
        dfswhite(0);// 找到一个解，解的数量加一
        return;
    }

然后判断的条件也增加为

if (checkblack(deep, i) && a[deep][i] != 0) （0不能放置）

void dfsblack(int deep) {
    if (deep == n) {
        dfswhite(0);// 找到一个解，解的数量加一
        return;
    }
    for (int i = 0; i < n; ++i) {
        // 尝试在当前行的每一列放置皇后
        if (checkblack(deep, i) && a[deep][i] != 0) {
            b[deep][i] = 1; // 放置皇后
            vis[deep][i] = true;
            dfsblack(deep + 1);// 递归搜索下一行
            b[deep][i] = 0; // 回溯，移除皇后
            vis[deep][i] = false;
        }
    }
}

dfswhite

检查白皇后是否能放的条件为：

checkwhite(deep, i) && a[deep][i] != 0 && b[deep][i] == 0 （0不能放置，黑放过不能放）

void dfswhite(int deep) {
    if (deep == n) {
        ans++;// 找到一个解，解的数量加一
        return;
    }
    
    for (int i = 0; i < n; ++i) {
        // 尝试在当前行的每一列放置皇后
        if (checkwhite(deep, i) && a[deep][i] != 0 && b[deep][i] == 0) {
            c[deep][i] = 1; // 放置皇后
            vis[deep][i] = true;
            dfswhite(deep + 1);// 递归搜索下一行
            c[deep][i] = 0; // 回溯，移除皇后
            vis[deep][i] = false;
        }
    }
}

int main() {
    cin >> n; 
    memset(vis, false, sizeof(vis));
    memset(c, 0, sizeof(c));
    memset(b, 0, sizeof(b));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    }
    dfsblack(0);// 从第0行开始深度优先搜索
    cout << ans;
    return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。