本文主要是介绍dfs算法复习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
深度优先算法 一条路走到黑
代码模版如下 将1~n 所有的排列组合方式 列举出来
代码模版
#include <iostream>using namespace std;
const int N = 10;
int n;
int path[N];
bool a[N];void def(int u)
{if (u == n){for (int i = 0; i < n; i++){cout << path[i] << ' ';}puts("");return;}for (int i = 1; i <= n; i++){if ( !a[i])//表示该数字还没有被使用{path[u] = i; //将该值赋给当前位置a[i] = true;//将该值标记为已使用def(u+1);//遍历下一位a[i] = false;}}
}int main()
{cin >> n;def(0);return 0;
}题目
n−皇后问题是指将 n个皇后放在 n×n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n行，每行输出一个长度为 n的字符串，用来表示完整的棋盘状态。其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。 注意：行末不能有多余空格。
数据范围：
1≤n≤9
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
代码
第一种方法思路比较正：
#include <iostream>using namespace std;
const int N = 1000;int n;
char a[N][N];
bool row[N], col[N], dg[N], udg[N];
void dfs(int x,int y,int num) // x表示行 y表示列 num 表示用了几个皇后
{if (y == n)//表示走到一行的最后一个{x++;y = 0;}//判断满足的条件if (x == n){if (num == n){for (int i = 0; i < n; i++){puts(a[i]);}puts("");}return;}//放皇后if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){a[x][y] = 'q';row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;dfs(x, y + 1,num + 1);row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;a[x][y] = '.';}//不放皇后dfs(x, y + 1, num);
}int main()
{cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)a[i][j] = '.';dfs(0, 0, 0);return 0;
}第二种方法
#include <iostream>using namespace std;
const int N = 1000;int n;
char q[N][N];bool st[N], dg[N], udg[N];
void dfs(int u)// 皇后的数量
{if (u == n){for (int i = 0; i < n; i++){puts(q[i]);}puts("");return;}for (int i = 0; i < n; i++){if (!st[i] && !dg[u + i] && !udg[i - u + n]){q[u][i] = 'q';st[i] = dg[u + i] = udg[i - u + n] = true;dfs(u + 1);st[i] = dg[u + i] = udg[i - u + n] = false;q[u][i] = '.';}}
}int main()
{cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)q[i][j] = '.';dfs(0);return 0;
}这篇关于dfs算法复习的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
