算法基础班–第三章–1.1.DFS——全排列搜索顺序
算法模板
DFS 无模板,最重要是考虑问题的搜索顺序
本题完整代码:
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];//对应_ _ _的状态,在往下搜索的过程中,会被逐渐填满
bool st[N]; // 填到某个位置时,哪些数已经被用过了 true表示被用过
void dfs(int u) {
if (u == n) { // 当走到第n个位置时候,说明被填满了,输出
for (int i = 0; i < n; i++) printf("%d ", path[i]);
puts("");
return ;
}
//当u<n说明还没有被填满
for (int i = 1; i <= n; i++) {
if (!st[i]) { //找到一个没有被用过的数,只有该数未被使用,才会用
path[u] = i; //枚举1~n中任意一个数,没被用,就填到_ _ _位置上去 第0层是根,第一层代表第1个位置#_ _ _,第二层代表第2个位置_ #_ _...
st[i] = true; //填上之后记录i被用过了
dfs(u + 1); //向下一层递归 当一层dfs()结束时,意味着已把下面所有路走完了,开始回溯(恢复现场)
st[i] = false;
// path[u] = 0; 去掉了,因为上面会不断覆盖path[u]
}
}
}
int main () {
cin >> n;
dfs(0); //从第0个位置开始看
return 0;
}