C语言dfs深度优先练习 N皇后 图文并茂超详解 ！_dfs经典题目c语言

如果你还没有dfs的基础，可以先看我的上一篇文章：C语言递归+DFS（深度优先搜索算法）详解

一.N皇后题目

 二.图文详解

我们先从四皇后开始，模拟一次dfs的搜索过程

第一排选择占（0，0），粉红线划的位置就不能选了。第二排此时可以占（1，2），（1，3）两个位置。我们先选择占（1，2）这个位置，此时我们发现第三排的位置都有标记不能选了，所以我们此时撞到了“南墙”，需要开始回溯。

回溯到状态①，我们选择第二排占（1，3）这个位置，欸此时我们发现第三排有位置可占了，我们占到（2，1）这个位置。但是很遗憾，我们用荧光笔标记后发现，第四排又没位置了，所以撞到了“南墙”开始回溯。此时就只能回溯到最初什么都没选的空白状态了。我们又开始占（0，1）这个位置，继续继续往下一排搜索......

这里提供一个成功的结果。

接着我们开始构思代码如何实现。 

1.已经决定用dfs了，那我们应该立马想到dfs的cp——状态数组。（请锁死这两位）

刚刚我们怎么模拟来着？我们一层一层往下搜的，那么这里可以用个for循环一层层的搜，这样我们就可以不用考虑“行”的冲突。

但是我们需要开一个某列是否已经有元素的状态数组，以及2个对角线状态数组（为什么是两个？你画个×）这样我们在判断一个位置是否可以占的时候，就检查这个位置的列状态数组，以及对角线状态数组。

2.问题又来了，列状态数组好办，如何构造对角线状态数组呐？

我们惊奇的发现，其实对于某一对角线上的元素，他们都有规律的。一条是：行号+列号为定值，一条是行号+总行数-列号为定值。这样我们就可以为某一条对角线开一个状态数组啦。

三.代码实现

哦对了，dfs还有位cp——恢复现场  记得写上它哦~  （你们三演燃冬吧）

#include <iostream>
using namespace std;
 
const int N = 20;
int n;
char res[N][N];
bool col[N], dg[N], udg[N];
 
void dfs(int u)//u为行
{
	if (u == n)
	{
		for (int i = 0; i < n; i++)
		{
			puts(res[i]);//puts输出自带换行
		}
        printf("\n");
		return;//回溯
	}
	for (int i = 0; i <n;  i++)//i代表列
	{
		if (!col[i] && !dg[u + i] && !udg[u+n-i])
		{
			res[u][i] = 'Q';
			col[i] = dg[u + i] = udg[u+n-i] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[u+n-i] = false;//恢复现场
			res[u][i] = '.';
		}
	}
 
 
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)//咱先把整个棋盘初始化一下
	{
		for (int j = 0; j < n; j++)
		{
			res[i][j] = '.';
		}
	}
	dfs(0);
 
	return 0;
}

OK，本篇文章就结束啦，别慌，接下来还会发关于dfs的练习，咱主打一个熟能生巧。有什么不懂欢迎评论区提问，溜了溜了~