DFS深搜之全排列（初学）

题目描述

以nyoj2.0 366题为例，记录入门dfs的代码，并理清思路，方便以后复习巩固，初学dfs如果有问题还请指出~

思路解析与dfs模板伪代码

void dfs() { //初学时基本为一个参数，根据题意添加
if (到达终点状态) {
…//根据题意添加
return; //重要！！！如果不return将卡进递归，不能寻找下一条路
}
if(越界或者是不合法状态)
return;
if(特殊状态)//剪枝
return ;
for (扩展方式) {
if (扩展方式所达到状态合法) {
修改操作;//根据题意来添加
标记；
dfs（）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}
}
} 

#include<iostream> #include<stdio.h> using namespace std; //x表示全排列的数字 //a[]存放每一条路的结果,b[]以01来判断手中有哪些数字  int x, a[20], b[20]; //step可看做放数字的盒子，从第一个盒子开始放数字  void dfs(int step) { //判断结束边界  if (step > x) { //并在寻找到结束边界时将结果打印出来  //数字是从1到x间排列，不应初始化为0  for (int i = 1; i <= x; i++) { cout << a[i]; } cout << endl; return; } //i->x后跳出循环即dfs结束  for (int i = 1; i <= x; i++) { //放入盒子的条件必须是数字在手里（未被放入这条路之前的盒子）  if (b[i] == 0) { //第step个盒子存放i  a[step] = i; //标记i已被使用  b[i] = 1; //递归调用，下一个盒子寻找存放的数字  dfs(step+1); //收回盒子里的数字才能进行下一次尝试 ！！  b[i] = 0; } } //控制dfs结束  return; } int main() { int N; scanf("%d", &N); while (N--) { scanf("%d", &x); //初始step=1，从第一个盒子开始放数字  dfs(1); } }

第一次写博客，有点不完善，慢慢改进，如果有错误请指出哦