DFS(深搜)
dfs 递归搜索树
如何用 dfs 解决全排列问题？
dfs 最重要的是搜索顺序。用什么顺序遍历所有方案。
对于全排列问题，以 n = 3 为例，可以这样进行搜索：
算法模板：
用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。
void dfs(int u) { if(u==n)// 一个排列填充完成 { for(int i=0;i<n;i++) if(u==n)cout<<path[i]<<" ";// 注意格式 别忘了每两个数字间用空格隔开 cout<<endl; return ; } for(int i=1;i<=n;i++) { if(!start[i]) { path[u]=i;// 把 i 填入数字排列的位置上 start[i]=1;// 表示该数字用过了 不能再用 dfs(u+1);//这个位置的数填好 递归到右面一个位置 start[i]=0;// 恢复现场 该数字后续可用 } } // for 循环全部结束了 dfs(u)才全部完成 回溯 }
例题：
1.排列数字：
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
#include<bits/stdc++.h> using namespace std; const int N=10; int path[N],start[N]; int n; void dfs(int u) { if(u==n)// 一个排列填充完成，就是叶节点 { for(int i=0;i<n;i++) if(u==n)cout<<path[i]<<" ";// 注意格式 别忘了每两个数字间用空格隔开 cout<<endl; return ; } for(int i=1;i<=n;i++) { if(!start[i]) { path[u]=i;// 把 i 填入数字排列的位置上 start[i]=1;// 表示该数字用过了 不能再用 dfs(u+1);//这个位置的数填好 递归到右面一个位置 start[i]=0;// 恢复现场 该数字后续可用 } } // for 循环全部结束了 dfs(u)才全部完成 回溯 } int main() { cin>>n; dfs(0);// 在path[0]处开始填数 }
2.n-皇后问题
n−皇后问题是指将 n 个皇后放在 n×n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
#include <bits/stdc++.h> 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 ++ ) cout << g[i] << endl; cout<<endl; // 换行 return; } // 枚举u这一行，搜索合法的列 int x = u; for (int y = 0; y < n; y ++ ) // 剪枝(对于不满足要求的点，不再继续往下搜索) if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) { col[y] = dg[y - x + n] = udg[y + x] = true; g[x][y] = 'Q'; dfs(x + 1); g[x][y] = '.'; // 恢复现场 col[y] = dg[y - x + n] = udg[y + x] = false; } } 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; }
BFS(广搜)
广度优先遍历。
思路：从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往前走第二步，记录下所有第二步能走到的点，重复下去，直到走到终点。输出步数即可。
这就是广度优先遍历的思路。
实现方式：广度优先遍历
用 g 存储地图，f存储起点到其他各个点的距离。
从起点开始广度优先遍历地图。
当地图遍历完，就求出了起点到各个点的距离，输出f[n][m]即可。
例题：
1.走迷宫
给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。
数据保证 (1,1)处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出样例：
8
图解：
void bfs(int a, int b): 广度优遍历函数。输入的是起点坐标。
queue q;：用来存储每一步走到的点。
while(!q.empty())循环：循环依次取出同一步数能走到的点，再往前走一步。
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};:一个点往下一步走得时候，可以往上下左右四方向走。
#include<bits/stdc++.h> using namespace std; const int N = 110; typedef pair<int, int> PII; int n, m; int g[N][N];//存放地图 int d[N][N];//存每一个点到起点的距离 PII Prev[N][N];//记录路径 int bfs() { queue<PII> q;//创造一个队列,用来存储每一步走到的点 q.push({0, 0});//插入(0,0)输入的是起点坐标 memset(d, -1, sizeof(d));//距离初始化为- 1表示没有走过 d[0][0] = 0;//表示起点走过了 //(0,0) 向上(-1,0) 向右(0,1) 向下(1,0) 向左(0,-1) int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//x 方向的向量和 y 方向的向量组成的上、右、下、左 while (q.size())//队列不为空 { PII t = q.front();//取队头元素 q.pop();//出队 for (int i = 0; i < 4; i++)//枚举4个方向 { int x = t.first + dx[i], y = t.second + dy[i];//x表示沿着此方向走会走到哪个点 //在边界内 并且是空地可以走 且之前没有走过 if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) { d[x][y] = d[t.first][t.second] + 1;//当前点到起点的距离 Prev[x][y] = t; q.push({x, y});//将新坐标入队 } } } int x = n - 1, y = m - 1; while(x || y)//有一个不等于0 { cout << x << ' ' << y << endl;//输出路径 PII t = Prev[x][y]; x = t.first, y = t.second; } return d[n-1][m-1]; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> g[i][j]; cout << bfs() << endl; return 0; }
2.八数码
在一个 3×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。
例如：
1 2 3 x 4 6 7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3 4 5 6 7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3 x 4 6 7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19
思路图解：
转以后：a = x + dx[i], b = y + dy[i].
思想：将每一种情况作为1个节点，目标情况即为终点
从初始状况移动到目标情况 —> 求最短路
3、问题
第一点：怎么表示一种情况使其能作为节点？
第二点：如何记录每一个状态的“距离”（即需要移动的次数）？
第三点：队列怎么定义，dist数组怎么定义？
4、解决方案
将 “3*3矩阵” 转化为 “字符串”
队列可以用 queue<string> //直接存转化后的字符串 dist数组用 unordered_map<string, int> //将字符串和数字联系在一起，字符串表示状态，数字表示距离
注意字符串与矩阵的转化（非常重要）
#include <bits/stdc++.h> using namespace std; int bfs(string start) { //定义目标状态 string end = "12345678x"; //定义队列和dist数组 queue<string> q; unordered_map<string, int> d; //初始化队列和dist数组 q.push(start); d[start] = 0; //转移方式 int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; while(q.size()) { //取出队头字符放到t中 string t = q.front(); //将队头清空 q.pop(); //记录当前状态的距离，如果是最终状态则返回距离 int distance = d[t]; if(t == end) return distance; //查询x在字符串中的下标，然后转换为在矩阵中的坐标 int k = t.find('x'); int x = k / 3, y = k % 3; for(int i = 0; i < 4; i++) { //求转移后x的坐标 int a = x + dx[i], b = y + dy[i]; //当前坐标没有越界，因为是三行三列的矩阵 if(a >= 0 && a < 3 && b >= 0 && b < 3) { //转移x swap(t[k], t[a * 3 + b]); //如果当前状态是第一次遍历，记录距离，入队 if(!d.count(t)) { d[t] = distance + 1; q.push(t); } //还原状态，为下一种转换情况做准备 swap(t[k], t[a * 3 + b]); } } } //无法转换到目标状态，返回-1 return -1; } int main() { string start; char c; //输入起始状态 for(int i = 0; i < 9; i++) { cin >> c; start += c; } cout << bfs(start) << endl; return 0; }
