搜索初步

博主： RearWaves
发布时间：2023 年 05 月 01 日
426 次浏览
5 条评论
4425字数
分类：算法设计

# 搜索1

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

## 1.1 深度优先搜索DFS

直男算法, 执着, 一定要追到最后才回头. 有时需要回溯和剪枝.

使用的数据结构: stack; 空间: $O(n)$, 不具有最短性.

### [842. 排列数字](https://www.acwing.com/problem/content/844/)

给定一个整数 n, 将数字 1∼n 排成一排, 按照字典序将所有的排列方法输出.

```c++
const int N = 10;
int n;
int path[N];	//记录访问的路径
bool st[N];		//记录是否被访问过
void dfs(int u) {
	if (u == n) {
		for (int i = 0; i < n; i++) printf("%d ", path[i]);
		puts("");
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!st[i]) {	//判断这个是是否被访问过
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			st[i] = false;
		}
	}
}

int main() {
	cin >> n;
	dfs(0);		//从0这个位置开始深搜
	return 0;
}
```

### [843. n-皇后问题](https://www.acwing.com/problem/content/845/)

将 n 个皇后放在 n×n 的国际象棋棋盘上, 使得皇后不能相互攻击到, 即任意两个皇后都不能处于同一行、同一列或同一斜线上.

输出格式: 每个解决方案占 n 行, 每行输出一个长度为 n 的字符串, 用来表示完整的棋盘状态. 其中 `.` 表示某一个位置的方格状态为空, `Q` 表示某一个位置的方格上摆着皇后. 每个方案输出完成后, 输出一个空行.

**方法一: 全排列思想,逐行判断皇后放在哪一列**

```c++
int n;
char g[N][N];	//存储图
bool col[N], dg[N], udg[N];	//判断每列,对角线,反对角线上是否有皇后

void dfs(int u) {
	if (u == n) {
		for (int i = 0; i < n; i++) puts(g[i]);
		puts("");
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!col[i] && !dg[u + i] && !udg[n - u + i]) {     //判断u行i列是否满足
            //u+i,n-u+i可以分别看作x+y=b,y-x=b的截距
            //一条对角线对应一个截距, 可以将这个截距映射到数组下标中
			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;
}
```

**方法二: 逐个枚举每一个点,放或者不放(更加原始的搜索方式,速度较慢)**

```c++
const int N = 20;
int n;
char g[N][N];	//存储图
bool row[N], col[N], dg[N], udg[N];	//判断每行,每列,对角线,反对角线上是否有皇后

void dfs(int x, int y, int s) {		//s为当前放置的皇后数量
	if (s > n) return;
	if (y == n) y = 0, x++;			//如果该行枚举出界,跳转到下一行第一个
	if (x == n)
	{
		if (s == n)
		{
			for (int i = 0; i < n; i++) puts(g[i]);
			puts("");
		}
		return;
	}
	g[x][y] = '.';
	//该处不放皇后
	dfs(x, y + 1, s);
	//该处放置皇后
	if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
	{
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
		g[x][y] = 'Q';
		dfs(x, y + 1, s + 1);
		g[x][y] = '.';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
	}
}

int main()
{
	cin >> n;
	dfs(0, 0, 0);	//从左上角开始枚举
	return 0;
}
```

## 1.2 宽度优先搜索BFS

海王算法, 稳重, 雨露均沾, 慢慢扩张.

使用的数据结构: queue; 空间: $O(2^n)$, 当权值为1时具有最短路.

**模板:**

```c++
初始状态入队;
while (queue不空){
	t < -队头;
	扩展队头;
}
```

### [844. 走迷宫](https://www.acwing.com/problem/content/846/)

给定一个n*m的二维整数数组, 用来表示一个迷宫, 数组中只包含0或1, 其中0表示可以走的路, 1表示不可通过的墙壁.

最初, 有一个人位于左上角(1, 1)处, 已知该人每次可以向上、下、左、右任意一个方向移动一个位置. 请问, 该人从左上角移动至右下角(n, m)处, 至少需要移动多少次.

数据保证(1, 1)处和(n, m)处的数字为0, 且一定至少存在一条通路.

**使用系统队列:**

```c++
const int N = 110;
int n, m;	//n,m的数据范围均为100
//g[N][N]用来存储迷宫, d[x][y]用来存储(x,y)这一点到坐标原点的距离
int g[N][N], d[N][N];
//q队列用来存储宽度优先搜素到的路径也就是走迷宫经过哪些点
queue <pair<int, int>> q;
int bfs()
{
	memset(d, -1, sizeof d); //将d数组所有元素初始化为-1
	d[0][0] = 0;		//位于原点时到原点的距离为0
	q.push({ 0,0 });	//将原点入队
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; //定义方向向量一共四个方向

while (q.size()) {	//当队列非空时执行循环
		auto t = q.front();
		q.pop();	//插入一个位置的同时会弹出一个位置保证循环可以正常终止
		for (int i = 0; i < 4; i++) {	//x,y都要四个方向,遍历四个方向
			int x = t.first + dx[i], y = t.second + dy[i]; //四个方向对应x,y坐标

if (x >= 0 && x < n && y < m && y >= 0 && g[x][y] == 0 && d[x][y] == -1) {
				d[x][y] = d[t.first][t.second] + 1;		//走到下一个点的同时距离加1
				q.push({ x,y });	//将该点入队
			}
		}
	}
	return d[n - 1][m - 1];		//递归回下一个点
}

int main()
{
	scanf("%d%d", &n, &m);	//输入迷宫的尺寸大小
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &g[i][j]); //输入迷宫
		}
	}
	cout << bfs() << endl; //输出宽度优先搜索结果
	return 0;
}
```

**手写模拟队列:**

```c++
const int N = 110;
int n, m;
int g[N][N];	//地图
int d[N][N];	//各点到起点的距离
PII q[N * N];	//手写模拟一个队列
int bfs() {
	int hh = 0, tt = 0;	//hh指向队头元素,tt指向队尾元素
	q[0] = { 0, 0 };
	memset(d, -1, sizeof(d));
	d[0][0] = 0;
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
	while (hh <= tt) {
		auto t = q[hh++];
		//枚举上下左右四个方向
		for (int i = 0; i < 4; i++) {
			int x = t.first + dx[i], y = t.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
				//注意d[x][y]==-1代表该点没有更新过距离,也就是没有走过
				d[x][y] = d[t.first][t.second] + 1;
				q[++tt] = { x,y };
			}
		}
	}
	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;
}
```

**拓展:**求出每个点的路径(开一个Prev数组,存放每一个点的前一个点).

```c++
const int N = 110;
int n, m;
int g[N][N];	//地图
int d[N][N];	//各点到起点的距离
PII q[N * N];	//手写模拟一个队列
PII Prev[N][N];//记录该点上一步的点
int bfs() {
	int hh = 0, tt = 0;	//hh指向队头元素,tt指向队尾元素
	q[0] = { 0, 0 };
	memset(d, -1, sizeof(d));
	d[0][0] = 0;
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
	while (hh <= tt) {
		auto t = q[hh++];
		//枚举上下左右四个方向
		for (int i = 0; i < 4; i++) {
			int x = t.first + dx[i], y = t.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
				//注意d[x][y]==-1代表该点没有更新过距离,也就是没有走过
				d[x][y] = d[t.first][t.second] + 1;
				Prev[x][y] = t;
				q[++tt] = { x,y };
			}
		}
	}
	//求路径的过程
	int x = n - 1, y = m - 1;
	while (x || y) {//只要x,y不同时为0,就继续向前转移
		cout << x << " " << y << endl;
		auto 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;
}
```

### [845. 八数码](https://www.acwing.com/problem/content/847/)

在一个 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
```

现在, 给你一个初始网格, 请你求出得到正确排列至少需要进行多少次交换.

```c++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;
int bfs(string start) {	
	//定义队列和dist数组并初始化
	queue<string> q;
	unordered_map<string, int> d;
	q.push(start);
	d[start] = 0;
	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
	string end = "12345678x";	//定义目标状态
	while (q.size()) {
		auto t = q.front();
		q.pop();
		if (t == end) return d[t];
		int distance = d[t];
		//查询x在字符串中的下标, 然后转换为在矩阵中的坐标
		int k = t.find('x');
		int x = k / 3, y = k % 3;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];	//求转移后x的坐标
			if (a >= 0 && a < 3 && b >= 0 && b < 3) {
				swap(t[a * 3 + b], t[k]);
				//如果当前状态是第一次遍历, 记录距离, 入队
				if (!d.count(t)) {
					d[t] = distance + 1;
					q.push(t);
				}
				swap(t[a * 3 + b], t[k]);	//还原状态, 为下一种转换情况做准备
			}
		}
	}
	return -1;	//无法转换到目标状态, 返回-1
}
int main() {
	char s[2];
	string start;	//表示开始的状态
	//string str, start;
	//while (cin >> str) start += str;
	for (int i = 0; i < 9; i++) {
		cin >> s;
		start += *s;
	}
	cout << bfs(start) << endl;
	return 0;
}

```

最后修改：2023 年 05 月 01 日