文章目录
- 排列数字
- n皇后问题
- 方法一
- 方法二
排列数字
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。
现在,按照字典序将所有的排列方法输出。
利用DFS解决全排列问题
dfs 最重要的是搜索顺序。用什么顺序遍历所有方案。
对于全排列问题,以 n = 3 为例,可以这样进行搜索:
用 path 数组保存排列,当排列的长度为 n 时,是一种方案,输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时:i 已经被用过,state[i] 为 0 时,i 没有被用过。
dfs(i) 表示的含义是:在 path[i] 处填写数字,然后递归的在下一个位置填写数字。
回溯:第 i 个位置填写某个数字的所有情况都遍历后, 第 i 个位置填写下一个数字。
假设有 3 个空位,从前往后填数字,每次填一个位置,填的数字不能和前面一样。
最开始的时候,三个空位都是空的:__ __ __
首先填写第一个空位,第一个空位可以填 1,填写后为:1 __ __
填好第一个空位,填第二个空位,第二个空位可以填 2,填写后为:1 2 __
填好第二个空位,填第三个空位,第三个空位可以填 3,填写后为: 1 2 3
这时候,空位填完,无法继续填数,所以这是一种方案,输出。
然后往后退一步,退到了状态:1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ,没有其他数字可以填。
因此再往后退一步,退到了状态:1 __ __。第二个空位上除了填过的 2,还可以填 3。第二个空位上填写 3,填写后为:1 3 __
填好第二个空位,填第三个空位,第三个空位可以填 2,填写后为: 1 3 2
其他4种结果依次类推
#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{if(u > n)//数字填完了,输出{for(int i = 1; i <= n; i++)//输出方案cout << path[i] << " ";cout << endl;}for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n{if(!state[i])//如果数字 i 没有被用过{path[u] = i;//放入空位state[i] = 1;//数字被用,修改状态dfs(u + 1);//填下一个位state[i] = 0;//回溯,取出 i}}
}int main()
{cin >> n;dfs(1);return 0;
}
n皇后问题
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n,请你输出所有的满足条件的棋子摆法。
经过上图的推理过程只将第一行的位置试探出来了,只需要进行逐个试探可以将所有的结果试探出来
方法一
(DFS按行枚举) 时间复杂度O(n!)
对角线 dg[u+i]dg[u+i],反对角线udg[n−u+i]udg[n−u+i]中的下标 u+i 和 n−u+i 表示的是截距
找一些合法的下标来表示dg 或udg 是否被标记过,所以如果你愿意,你取 udg[n+n−u+i] 也可以,只要所有(u,i)对可以映射过去就行
#include <iostream>
using namespace std;
const int N = 20; // bool数组用来判断搜索的下一个位置是否可行
// col列,dg对角线,udg反对角线
// g[N][N]用来存路径int n;
char g[N][N];
bool col[N], dg[N], udg[N];void dfs(int u) {// u == n 表示已经搜了n行,故输出这条路径if (u == n) {for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;puts(""); // 换行return;}//对n个位置按行搜索for (int i = 0; i < n; i ++ )// 剪枝(对于不满足要求的点,不再继续往下搜索) // udg[n - u + i],+n是为了保证下标非负if (!col[i] && !dg[u + i] && !udg[n - u + i]) {g[u][i] = 'Q';col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);col[i] = dg[u + i] = udg[n - u + i] = false; // 恢复现场 这步很关键g[u][i] = '.';}
}int main() {cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
}
方法二
(DFS按每个元素枚举)时间复杂度O(2n2)
时间复杂度分析:每个位置都有两种情况,总共有 n2个位置
// 不同搜索顺序 时间复杂度不同 所以搜索顺序很重要!
#include <iostream>
using namespace std;
const int N = 20;int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // 因为是一个个搜索,所以加了row// s表示已经放上去的皇后个数
void dfs(int x, int y, int s)
{// 处理超出边界的情况if (y == n) y = 0, x ++ ;if (x == n) { // x==n说明已经枚举完n^2个位置了if (s == n) { // s==n说明成功放上去了n个皇后for (int i = 0; i < n; i ++ ) puts(g[i]);puts("");}return;}// 分支1:放皇后if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {g[x][y] = 'Q';row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;dfs(x, y + 1, s + 1);row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;g[x][y] = '.';}// 分支2:不放皇后dfs(x, y + 1, s);
}int main() {cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0, 0, 0);return 0;
}