广度优先搜索 BFS

算法特点

每一步距离是1，每个状态比较小，求最小距离
队列

如果每一步是1，那么不需要使用 priority_queue 就可以实现优先队列的效果（距离小的在距离大的之前

深度优先搜索 DFS
状态总数有限，每个状态比较大
递归（可以自己用非递归和栈实现）

有多少个连通块？
每个连通块多大？

struct Node
{
	int first, second;
}a, b;

a < b;
max(a, b);

基本代码

所有点距离初始化成 -1
起点距离初始化成0
起点加入队列
while 队列非空
	拿出队首的点
	枚举队首的点 能到的点 (这里常常使用方向数组)
		如果 能到的点 的距离 是 -1： 如果到过一定不能更新，如果没到过距离一定是最小值
			能到的点 的距离 = 队首的点 的距离 + 1
			能到的点 加入 队列
如果终点的距离是 -1：
	到不了
否则
	终点的距离是答案

01BFS

所有点距离初始化成 无穷大
起点距离初始化成0
起点加入队列
while 队列非空
	拿出队首的点
	枚举队首的点 能到的点 (这里常常使用方向数组)
		如果 能到的点 的距离 > 队首的点 的距离 + 1  （同一个点是有可能被更新2次的，同一个至多被更新2次）
			能到的点 的距离 = 队首的点 的距离 + 1
			如果这条边是 0
				能到的点 加入 队首
			如果这条边是 1
				能到的点 加入 队尾
			（同一个点是有可能入队列2次的，同一个至多入队列2次）
如果终点的距离是 -1：
	到不了
否则
	终点的距离是答案

参考题目

P1443 马的遍历

https://www.luogu.com.cn/problem/P1443

题目描述

有一个 n×mn \times m 的棋盘，在某个点 (x,y)(x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n,m,x,yn, m, x, y。

输出格式

一个 n×mn \times m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 55 格，不能到达则输出 −1-1）。

样例 #1

样例输入 #1
3 3 1 1
样例输出 #1
0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 1≤x≤n≤4001 \leq x \leq n \leq 400，1≤y≤m≤4001 \leq y \leq m \leq 400。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int d[401][401];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
bool in(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
int main() {
	cin >> n >> m >> x >> y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = -1;
		}
	}
	d[x][y] = 0;
	queue<int> q;
	q.push(x);
	q.push(y);
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (in(nx, ny)) {
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			printf("%-5d", d[i][j]);
		}
		printf("\n");
	}
	return 0;
}

题解

P1747 好奇怪的游戏

https://www.luogu.com.cn/problem/P1747

题目背景

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

题目描述

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？

输入格式

第1行：两个整数x1，y1

第2行：两个整数x2，y2

输出格式

第1行：黑马到1,1的步数

第2行：白马到1,1的步数

样例 #1

样例输入 #1
12 16
18 10
样例输出 #1
8 
9

提示

100%数据：x1,y1,x2,y2<=20

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int d[40][40];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2, 2, 2, -2, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1, 2, -2, 2, -2};
bool in(int x, int y) {
	return 1 <= x && x < 40 && 1 <= y && y < 40;
}
int main() {
	for (int i = 0; i < 40; i++) {
		for (int j = 0; j < 40; j++) {
			d[i][j] = -1;
		}
	}
	d[1][1] = 0;
	queue<int> q;
	q.push(1);
	q.push(1);
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 12; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (in(nx, ny)) {
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
	cin >> x >> y;
	cout << d[x][y] << endl;
	cin >> x >> y;
	cout << d[x][y] << endl;
	return 0;
}

题解

P1746 离开中山路

https://www.luogu.com.cn/problem/P1746

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在x1,y1处，车站在x2,y2处。现在给出一个n×n（n<=1000）的地图，0表示马路，1表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（a[i][j]距离为1）。你能帮他解决吗？

输入格式

第1行：一个数 n

第2行~第n+1行：整个地图描述（0表示马路，1表示店铺，注意两个数之间没有空格）

第n+2行：四个数 x1,y1,x2,y2

输出格式

只有1行：最短到达目的地距离

样例 #1

样例输入 #1
3
001
101
100
1 1 3 3
样例输出 #1
4

提示

20%数据：n<=100

100%数据：n<=1000

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[1002][1002];
int d[1002][1002];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int n;
bool in(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
}
void bfs(int x, int y) {
	queue<int> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = -1;
		}
	}
	d[x][y] = 0;
	q.push(x);
	q.push(y);
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			char ch = s[nx][ny];
			if (in(nx, ny) && ch != '1') {
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	int x, y;
	cin >> x >> y;
	x--;
	y--;
	bfs(x, y);
	cin >> x >> y;
	x--;
	y--;
	cout << d[x][y] << endl;
	return 0;
}

题解

P2298 Mzc和男家丁的游戏

https://www.luogu.com.cn/problem/P2298

题目背景

ｍｚｃ与ｄｊｎ的第二弹。

题目描述

ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过上一弹的都知道）。他把她们召集在了一起，他们决定玩捉迷藏。现在mzc要来寻找他的男家丁，大家一起来帮忙啊！

由于男家丁数目不多，再加上mzc大大的找人【laopo】水平很好，所以一次只需要找一个男家丁。

输入格式

第一行有两个数ｎ，m，表示有n行m列供男家丁躲藏，

之后n行m列的矩阵，‘m‘表示mzc，‘d’表示男家丁，‘#’表示不能走，‘.‘表示空地。

输出格式

一行，若有解：一个数ｓｕｍ，表示找到男家丁的最短移动次数。

若无解：输出“No Way!”。

样例 #1

样例输入 #1
5 6
.#..#.
....#.
d.....
#####.
m.....
样例输出 #1
12

提示

3=<M,n<=2000

由于mzc大大十分着急，所以他只能等待1S。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[2002][2002];
int d[2002][2002];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int n, m;
bool in(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < m;
}
void bfs(int x, int y) {
	queue<int> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			d[i][j] = -1;
		}
	}
	d[x][y] = 0;
	q.push(x);
	q.push(y);
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			char ch = s[nx][ny];
			if (in(nx, ny) && ch != '#') {
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					if (ch == 'd') {
						printf("%d\n", d[nx][ny]);
						return;
					}
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
	printf("No Way!\n");
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	int x, y;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] == 'm') {
				x = i;
				y = j;				
			}
		}
	}
	bfs(x, y);
	return 0;
}

题解

P1332 血色先锋队

https://www.luogu.com.cn/problem/P1332

题目背景

巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。

题目描述

军团是一个 nn 行 mm 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。

输入格式

第 11 行：四个整数 nn，mm，aa，bb，表示军团矩阵有 nn 行 mm 列。有 aa 个感染源，bb 为血色敢死队中领主的数量。

接下来 aa 行：每行有两个整数 xx，yy，表示感染源在第 xx 行第 yy 列。

接下来 bb 行：每行有两个整数 xx，yy，表示领主的位置在第 xx 行第 yy 列。

输出格式

第 11 至 bb 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 00。

样例 #1

样例输入 #1
5 4 2 3
1 1
5 4
3 3
5 3
2 4
样例输出 #1
3
1
3

提示

输入输出样例 1 解释

如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。

数据规模与约定

对于 100%100\% 的数据，保证 1≤n,m≤5001\le n,m\le500，1≤a,b≤1051\le a,b\le10^5。

参考代码

#include <bits/stdc++.h>
using namespace std;
int d[501][501];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int n, m, A, B, x, y;
bool in(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
int main() {
	scanf("%d%d%d%d", &n, &m, &A, &B);
	queue<int> q;
	memset(d, -1, sizeof d);
	for (int i = 0; i < A; i++) {
		scanf("%d%d", &x, &y);
		d[x][y] = 0;
		q.push(x);
		q.push(y);
	}
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (in(nx, ny) ) {
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
	for (int i = 0; i < B; i++) {
		scanf("%d%d", &x, &y);
		printf("%d\n", d[x][y]);
	}
	return 0;
}

题解

P1825 [USACO11OPEN]Corn Maze S

https://www.luogu.com.cn/problem/P1825

题目描述

This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide's start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.

The outside of the corn maze is entirely corn except for a single exit.

The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:

* Corn (corn grid elements are impassable)

* Grass (easy to pass through!)

* A slide endpoint (which will transport a cow to the other endpoint)

* The exit

A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the 'at' symbol (@). What is the minimum time she needs to move to the exit space?

去年秋天，奶牛们去参观了一个玉米迷宫，迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用：一头奶牛可以从这个装置的起点立即到此装置的终点，同时也可以从终点出发，到达这个装置的起点。如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。

玉米迷宫的外部完全被玉米田包围，除了唯一的一个出口。

这个迷宫可以表示为N×M的矩阵(2 ≤ N ≤ 300; 2 ≤ M ≤ 300)，矩阵中的每个元素都由以下项目中的一项组成：

 玉米，这些格子是不可以通过的。

 草地，可以简单的通过。

 一个装置的结点，可以将一头奶牛传送到相对应的另一个结点。

 出口

奶牛仅可以在相邻两个格子之间移动，要在这两个格子不是由玉米组成的前提下才可以移动。奶牛能在一格草地上可能存在的四个相邻的格子移动。从草地移动到相邻的一个格子需要花费一个单位的时间，从装置的一个结点到另一个结点需要花费0个单位时间。

被填充为玉米的格子用“#”表示，草地用“.”表示，每一对装置的结点由相同的大写字母组成“A-Z”，且没有两个不同装置的结点用同一个字母表示，出口用“=”表示。

Bessie在这个迷宫中迷路了，她知道她在矩阵中的位置，将Bessie所在的那一块草地用“@”表示。求出Bessie需要移动到出口处的最短时间。

例如以下矩阵，N=5，M=6：

###=##
#.W.##
#.####
#.@W##
######

唯一的一个装置的结点用大写字母W表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费0个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了3个单位时间。

输入格式

第一行：两个用空格隔开的整数N和M；

第2-N+1行：第i+1行描述了迷宫中的第i行的情况（共有M个字符，每个字符中间没有空格。）

输出格式

一个整数，表示Bessie到达终点所需的最短时间。

样例 #1

样例输入 #1
5 6
###=##
#.W.##
#.####
#.@W##
######
样例输出 #1
3

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[302][302];
int d[302][302];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int tx[256];
int ty[256];
int n, m;
bool in(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < m;
}
int bfs(int x, int y) {
	queue<int> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			d[i][j] = -1;
		}
	}
	d[x][y] = 0;
	q.push(x);
	q.push(y);
	while (q.size()) {
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			char ch = s[nx][ny];
			if (in(nx, ny) && ch != '#') {
				if (isalpha(ch)) {
					nx ^= tx[ch];
					ny ^= ty[ch];
				}
				if (d[nx][ny] == -1) {
					d[nx][ny] = d[x][y] + 1;
					if (s[nx][ny] == '=') {
						return d[nx][ny];
					}
					q.push(nx);
					q.push(ny);
				}
			}
		}
	}
	return -1;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	int sx = -1;
	int sy = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '@') {
				s[i][j] = '.';
				sx = i;
				sy = j;
			}
			if (isalpha(s[i][j])) {
				tx[s[i][j]] ^= i;
				ty[s[i][j]] ^= j;
			}
		}
	}
	printf("%d\n", bfs(sx, sy));
	return 0;
}

题解

xor
(a ^ a) == 0
(a ^ b) == (b ^ a)
(a ^ b) ^ c == a ^ (b ^ c)

a ^ b ^ a = b

(x1, y1) (x2, y2)

given x, y, we know (x, y) is (x1, y1) or (x2, y2)
we want to get another

(x1 ^ x2 ^ x, y1 ^ y2 ^ y)
(x1 + x2 - x, y1 + y2 - y)

#include <bits/stdc++.h>
using namespace std;
char s[302][302];
int d[302][302];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int tx[256];
int ty[256];
int n, m;
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
int bfs(int x, int y) {
    queue<int> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            d[i][j] = -1;
        }
    }
    d[x][y] = 0;
    q.push(x);
    q.push(y);
    while (q.size()) {
        x = q.front();
        q.pop();
        y = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            char ch = s[nx][ny];
            if (in(nx, ny) && ch != '#') {
                if (isalpha(ch)) {
                    nx ^= tx[ch];
                    ny ^= ty[ch];
                }
                if (d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    if (s[nx][ny] == '=') {
                        return d[nx][ny];
                    }
                    q.push(nx);
                    q.push(ny);
                }
            }
        }
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    int sx = -1;
    int sy = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i][j] == '@') {
                s[i][j] = '.';
                sx = i;
                sy = j;
            }
            if (isalpha(s[i][j])) {
                tx[s[i][j]] ^= i;
                ty[s[i][j]] ^= j;
            }
        }
    }
    printf("%d\n", bfs(sx, sy));
    return 0;
}
  1. 广度优先搜索 BFS
    1. 算法特点
      1. 基本代码
      2. 01BFS
    2. 参考题目
      1. P1443 马的遍历
      2. P1747 好奇怪的游戏
      3. P1746 离开中山路
      4. P2298 Mzc和男家丁的游戏
      5. P1332 血色先锋队
      6. P1825 [USACO11OPEN]Corn Maze S
≡