图论——图的搜索_Alex_McAvoy的博客-CSDN博客
语雀版本
1 深度优先搜索DFS
1. 从图中某个顶点 v0 出发，首先访问 v0 2. 访问结点 v0 的第一个邻接点，以这个邻接点 vt 作为一个新节点，访问 vt 所有邻接点，直到以 vt 出发的所有节点都被访问 3. 回溯到 v0 的下一个未被访问过的邻接点，以这个邻结点为新节点，重复步骤 2，直到图中所有与 v0 相通的所有节点都被访问 4. 若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点，重复步骤 1，直到图中的所有节点均被访问
int vis[N];
void DFS(int i) {
for(所有i的邻接点j) {
if(!vis[j]) {
if(j == 目标状态)
return true;
vis[j]=true;
dfs(j);
}
}
}
2 广度优先搜索
1. 从图中某个顶点 v0 出发，首先访问 v0，将 v0 加入队列 2. 将队首元素的未被访问过的邻接点加入队列，访问队首元素并将队首元素出队，直到队列为空 3. 若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点，重复步骤 1，直到图中的所有节点均被访问过
bool vis[N];
void BFS(int start) {
queue<int> Q;
Q.push(start);
vis[start]=true;
while(!Q.empty()) {
int x=Q.front();
Q.pop();
if(x==目标状态) {
...
}
for(所有i的邻接点j) {
if(!vis[j]) {
Q.push(j);
vis[j]=true;
}
}
}
}
3 奇偶剪枝
3.1 无障碍物
上述的+为转弯、|为竖走，—为横走。s到e的最短路径为step_min= abs(ex-sx)+abs(ey-sy) =8。
如果走非最短路径，如下：
此时，step为14。step-step_min=6，为偶数。
性质：如果t-step_min为奇数，则不可能在t步从s到达e。
3.2 有障碍
上述的#表示无障碍。
上述的黑色为最短路径，红色+蓝色为别的路径。
可以发现，蓝色部分是最短路径的平移；红色部分则分为对称的2个，一个是远离E一个是接近E，所以是偶数。
性质：t-step_min为偶数时，该路径可能到达。
4 例题
4.1 深度优先搜索
红与黑
```cpp 【题目描述】 有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。【输入】
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
【输出】
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
【输入样例】
6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
0 0
【输出样例】
45
这道题比较常规
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)//一直读取，直到键盘输入遇到EOF或0 0结束while循环。
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis)); //为数组赋值0
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}
骨头的诱惑
```cpp 题目描述： 小狗在一个古老的迷宫中发现了一块骨头，这让它非常着迷。然而，当它捡起骨头时，迷宫开始震动，地面似乎在下沉。它意识到骨头是一个陷阱，急忙试图逃出这个迷宫。迷宫是一个大小为 N×M 的矩形。迷宫里有一个门，起初是关闭的，直到第 T 秒时才会打开，但仅仅打开不到 1 秒。因此，小狗必须准确在第 T 秒到达门的位置。在每一秒钟内，小狗可以移动到相邻的上、下、左或右的一个方块。一旦它进入某个方块，这个方块的地面在下一秒钟会开始下沉并消失。它不能在一个方块上停留超过 1 秒，也不能移动到已经访问过的方块。你能帮助这只可怜的小狗生存下来吗？
输入：
输入由多个测试用例组成。每个测试用例的第一行包含三个整数 N、M 和 T（1 < N, M < 7；0 < T < 50），分别表示迷宫的大小和门打开的时间。接下来的 N 行描述迷宫布局，每行包含 M 个字符。每个字符可能是以下几种之一：
‘X’：墙壁，狗无法进入；
‘S’：小狗的起点；
‘D’：门的位置；
‘.’：空白方块。
输入以三个零 0 0 0 结束，表示不再处理该测试用例。
输出：
对于每个测试用例，如果小狗能成功逃脱，输出 “YES”；否则输出 “NO”。
输入样例
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
…D
0 0 0
输出样例
NO
YES
在dfs过程中，进行了奇偶剪枝，加快判别。
```cpp
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int m, n, t;
char maps[10][10];
int vis[10][10];
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool flag;
struct node {
int x;
int y;
} start, endd;
bool judge(int x, int y) { // 判断是否越界
if (x < 0 || x >= m || y < 0 || y >= n || maps[x][y] == 'X' || vis[x][y])
return false;
return true;
}
void dfs(int x0, int y0, int time) {
if (maps[x0][y0] == 'D') { // 到达终点
if (time == t) { // 花费时间恰好等于要求的时间
flag = true; // 成功逃脱
return;
}
return;
}
if (flag) return; // 如果已经找到解，则直接返回
// 奇偶剪枝
int step = abs(x0 - endd.x) + abs(y0 - endd.y);
if ((t - step - time) % 2 != 0 || step + time > t)
return;
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int x = x0 + direction[i][0];
int y = y0 + direction[i][1];
if (judge(x, y)) { // 判断新坐标是否可行
vis[x][y] = 1; // 标记为已走过
time++; // 时间增加
dfs(x, y, time); // 递归搜索
vis[x][y] = 0; // 回溯
time--; // 时间回退
}
}
}
int main() {
while (cin >> m >> n >> t) {
if (m == 0 && n == 0 && t == 0) break;
memset(vis, 0, sizeof(vis));
flag = false;
for (int i = 0; i < m; i++) {
cin >> maps[i];
for (int j = 0; j < n; j++) {
if (maps[i][j] == 'S') {
start.x = i;
start.y = j;
vis[i][j] = 1;
}
if (maps[i][j] == 'D') {
endd.x = i;
endd.y = j;
}
}
}
// 开始时进行奇偶剪枝
int begins = abs(endd.x - start.x) + abs(endd.y - start.y);
if ((begins + t) % 2 != 0) {
cout << "NO" << endl;
continue;
}
dfs(start.x, start.y, 0);
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
4.2 广度优先搜索
仙岛求药
```cpp 【题目描述】 少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。下图 显示了一个迷阵的样例及李逍遥找到仙药的路线。
【输入】
输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1)‘@’：少年李逍遥所在的位置；
2)‘.’：可以安全通行的方格；
3)‘#’：有怪物的方格；
4)‘*’：仙药所在位置。
当在一行中读入的是两个零时，表示输入结束。
【输出】
对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。
【输入样例】
8 8
.@##…#
#…#.#
#.#.##…
…#.###.
#.#…#.
…###.#.
…#.…
.#…###
6 5
..#.
.#…
…##.
…
.#…
…@
9 6
.#…#.
.#.*.#
.####.
…#…
…#…
…#…
…#…
#.@.##
.#…#.
0 0
【输出样例】
10
8
-1
常规的BFS
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f // 定义一个足够大的值，表示无穷大
#define PI acos(-1.0) // 定义圆周率
#define N 26 // 定义迷宫的最大尺寸
#define MOD 2520
#define E 1e-12 // 定义极小的误差值
using namespace std;
int r, c; // r 表示迷宫的行数, c 表示迷宫的列数
char a[N][N]; // a 用来存储迷宫的字符信息
bool vis[N][N]; // vis 用来记录迷宫的访问状态
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 定义四个方向，上下左右
// 定义一个结构体，表示当前节点的位置和步数
struct node {
int x;
int y;
int step;
} q[N * 100]; // 定义一个队列，存储 BFS 过程中扩展的节点
// BFS 函数，寻找从 (sx, sy) 到 (ex, ey) 的最短路径
void bfs(int sx, int sy, int ex, int ey) {
int head = 1, tail = 1; // 定义队列的头部和尾部
bool flag = true; // flag 用来标记是否找到仙药
memset(vis, 0, sizeof(vis)); // 初始化访问数组，所有点初始都未访问
// 起始点入队，并标记已访问
vis[sx][sy] = 1;
q[tail].x = sx;
q[tail].y = sy;
q[tail].step = 0; // 起始点的步数为 0
tail++;
// 开始 BFS 搜索
while (head < tail) {
int x = q[head].x; // 当前处理的节点的横坐标
int y = q[head].y; // 当前处理的节点的纵坐标
int step = q[head].step; // 当前节点的步数
// 如果当前节点是终点 (仙药所在位置)，输出步数，结束搜索
if (x == ex && y == ey) {
flag = false;
printf("%d\n", step);
break;
}
// 扩展四个方向的节点
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0]; // 新节点的横坐标
int ny = y + dir[i][1]; // 新节点的纵坐标
// 判断新节点是否在迷宫内，是否未访问过，并且该位置是安全通行的
if (nx >= 0 && nx < r && ny >= 0 && ny < c && vis[nx][ny] == 0 && a[nx][ny] == '.') {
vis[nx][ny] = 1; // 标记新节点为已访问
q[tail].x = nx; // 新节点入队
q[tail].y = ny;
q[tail].step = step + 1; // 步数增加
tail++;
}
}
head++; // 队列头部前移
}
// 如果 flag 仍为 true，表示无法到达终点，输出 -1
if (flag)
printf("-1\n");
}
int main() {
int sx, sy, ex, ey; // sx, sy 表示起点坐标；ex, ey 表示终点（仙药）坐标
// 读入多组测试数据
while (scanf("%d%d", &r, &c) != EOF && (r || c)) {
// 读入迷宫地图
for (int i = 0; i < r; i++)
scanf("%s", a[i]);
// 查找起点 '@' 和终点 '*' 的位置
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (a[i][j] == '@') { // 起点
sx = i;
sy = j;
}
if (a[i][j] == '*') { // 终点
ex = i;
ey = j;
a[i][j] = '.'; // 将终点标记为可通行，以便 BFS 扩展
}
}
// 使用 BFS 寻找最短路径
bfs(sx, sy, ex, ey);
}
return 0;
}
流星雨
```cpp 贝西听说即将发生一场非凡的流星雨。据报道，这些流星会坠入地球，并摧毁它们撞击的任何地方。担心自己的安全，她发誓要找到一个安全的地方（一个不会被流星摧毁的地方）。目前，她在坐标平面的原点上吃草，并希望避开被流星摧毁的区域，前往一个安全的地方。报告说，会有 M 颗流星（1 ≤ M ≤ 50,000）坠落，其中第 i 颗流星会在时间 Ti（0 ≤ Ti ≤ 1,000）击中点 (Xi, Yi)（0 ≤ Xi ≤ 300；0 ≤ Yi ≤ 300）。每颗流星不仅会摧毁它击中的点，还会摧毁与该点相邻的四个格子。
贝西从时间 0 开始离开原点，能够以每秒一个单位的速度沿坐标轴方向移动到第一象限中的相邻四个格子之一（每个格子与上下左右相邻）。她无法在某个位置待到该位置被流星击中或之后。请确定贝西到达安全地点所需的最少时间。
输入
第一行：一个整数 M，表示流星的数量。
接下来的 M 行：每行包含三个整数 Xi, Yi, Ti，分别表示流星击中位置的坐标 (Xi, Yi) 和击中的时间 Ti。
输出
输出一行，包含贝西到达安全地点所需的最少时间；如果无法到达安全地点，则输出 -1。
输入样例
4
0 0 2
2 1 2
1 1 2
0 3 5
输出样例
5
<font style="color:rgb(77, 77, 77);">先建图，储存好每个点遭受流星打击的时间，不受打击的点用-1。因为开始时可能遭受打击，所以需要判别一开始受不受打击。然后bfs遍历整张图，找不受打击的点即可，因为要求最短时间，注意判重。</font>
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f // 定义一个较大的值，表示无穷大
#define PI acos(-1.0) // 定义 PI 的值
#define N 340 // 最大坐标值 + 安全边界
#define MOD 123
#define E 1e-6 // 定义一个极小的误差值
using namespace std;
int g[N][N]; // g[x][y] 表示位置 (x, y) 被流星击中的时间，-1 表示安全
int dir[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向的移动坐标，上下左右，另外加上 (0,0)
int vis[N][N]; // 访问标记数组，用于标记某个点是否已经被访问过
// 定义 BFS 的节点结构
struct Node {
int x; // 当前的横坐标
int y; // 当前的纵坐标
int step; // 从起点到达当前点所需的步数
};
// 广度优先搜索（BFS）函数，用于找到到达安全地点的最小时间
int bfs() {
if (g[0][0] == 0) // 起点 (0, 0) 被流星立即击中，无法开始移动
return -1;
if (g[0][0] == -1) // 如果起点是安全的，并且永远不会被击中
return 0;
queue<Node> q; // 定义 BFS 队列
Node a, temp; // 定义当前节点和临时节点
temp.x = 0; // 从原点开始
temp.y = 0;
temp.step = 0;
q.push(temp); // 将起点压入队列
// 开始 BFS 搜索
while (!q.empty()) {
a = q.front(); // 取出队列的第一个元素
q.pop();
// 遍历四个方向的相邻节点
for (int i = 1; i < 5; i++) {
temp.x = a.x + dir[i][0]; // 新的横坐标
temp.y = a.y + dir[i][1]; // 新的纵坐标
temp.step = a.step + 1; // 新的步数
// 如果新位置超出地图范围，跳过
if (temp.x < 0 || temp.y < 0 || temp.x >= N || temp.y >= N)
continue;
// 如果到达安全地点，返回步数
if (g[temp.x][temp.y] == -1)
return temp.step;
// 如果到达的时间大于或等于该点被毁坏的时间，跳过
if (temp.step >= g[temp.x][temp.y])
continue;
// 更新当前点的步数，并加入队列
g[temp.x][temp.y] = temp.step;
q.push(temp);
}
}
return -1; // 如果遍历完所有节点仍未找到安全地点，则返回 -1
}
int main() {
int n; // 流星数量
while (scanf("%d", &n) != EOF) {
memset(g, -1, sizeof(g)); // 初始化所有位置为安全状态（-1）
// 读取流星信息，并更新受影响的区域
while (n--) {
int x, y, t;
scanf("%d%d%d", &x, &y, &t); // 读取流星的坐标 (x, y) 和时间 t
// 更新流星击中位置的时间
if (g[x][y] == -1)
g[x][y] = t;
else
g[x][y] = min(g[x][y], t);
// 更新周围四个相邻格子受影响的时间
for (int i = 0; i < 5; i++) {
int nx = x + dir[i][0]; // 新的横坐标
int ny = y + dir[i][1]; // 新的纵坐标
if (nx < 0 || nx >= N || ny < 0 || ny >= N) // 检查是否越界
continue;
if (g[nx][ny] == -1) // 如果该位置未受影响，则设置为 t
g[nx][ny] = t;
else // 如果该位置已受影响，取较小的时间值
g[nx][ny] = min(t, g[nx][ny]);
}
}
// 执行 BFS 查找最短路径并输出结果
int res = bfs();
printf("%d\n", res);
}
return 0;
}
