参考《算法竞赛进阶指南》、AcWing题库

广度优先搜索

在树与图的遍历中, 我们介绍了图的广度优先遍历, 在深度优先搜索节中, 我们又定义了深度优先搜索过程产生的 “搜索树” 结构。如果我们把问题状态空间类比成一张图, 那么广度优先搜索就相当于对这张图的广度优先遍历。类似地, 我们依然借助一个队列来实现广度优先搜索, 起初, 队列中仅包含起始状态。在广度优先搜索的过程中, 我们不断从队头取出状态, 对于该状态面临的所有分支, 把沿着每条分支到达的下一个状态 (如果尚未访问过或者能够被更新成更优的解) 插入队尾。重复执行上述过程直到队列为空。

172. 立体推箱子（走地图）

题目描述

立体推箱子是一个风靡世界的小游戏。

游戏地图是一个 NN 行 MM 列的矩阵，每个位置可能是硬地（用 . 表示）、易碎地面（用 E 表示）、禁地（用 # 表示）、起点（用 X 表示）或终点（用 O 表示）。

你的任务是操作一个 1×1×21×1×2 的长方体。

这个长方体在地面上有两种放置形式，“立”在地面上（1×11×1 的面接触地面）或者“躺”在地面上（1×21×2 的面接触地面）。

在每一步操作中，可以按上下左右四个键之一。

按下按键之后，长方体向对应的方向沿着棱滚动 9090 度。

任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。

字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。

地图上唯一的一个字符 O 标识目标位置。

求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。

在移动过程中，X 和 O 标识的位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包括两个整数 NN 和 MM。

接下来 NN 行用来描述地图，每行包括 MM 个字符，每个字符表示一块地面的具体状态。

当输入用例 N=0，M=0N=0，M=0 时，表示输入终止，且该用例无需考虑。

输出格式

每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。

每个结果占一行。

数据范围

3≤N,M≤5003 \le N,M \le 500

输入样例：

1
2
3
4
5
6
7
8
9
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

输出样例：

1
10

算法分析

这是一道典型的 “走地图” 类问题, 也就是形如 “给定一个矩形地图, 控制一个物体在地图中按要求移动, 求最少步数” 的问题。广度优先搜索很擅长解决这种问题——地图的整体形态是固定不变的, 只有少数个体或特征随着每一步操作发生改变。我们只需要把这些变化的部分提取为状态, 把起始状态加入队列, 使用广度优先搜索不断取出队头状态, 沿着分支扩展、入队即可。广度优先搜索是逐层遍历搜索树的算法, 所有状态按照入队的先后顺序具有层次单调性 (也就是步数单调性)。如果每一次扩展恰好对应一步, 那么当一个状态第一次被访问 (入队) 时, 就得到了从起始状态到达该状态的最少步数。

在这道题目中, 不变的是整个地图, 变化的部分有长方体的位置和放置形态。我们可以用一个三元组 (x,y,lie)(x, y, l i e) 代表一个状态 (搜索树中的一个节点), 其中 lie=0lie=0 表示长方体立在 (x,y)(x, y); lie=1lie=1 表示长方体横向躺着, 左半部分位置在 (x,y)(x, y); lie=2lie=2 表示长方体纵向躺着, 上半部分在 (x,y)(x, y), 并用数组 d[x][y][lie]d[x][y][l i e] 记录从起始状态到达每个状态的最少步数。然后执行广度优先搜索即可。为了程序实现方便, 我们用数字 0∼30 \sim 3 分别代指左、右、上、下四个方向。

提示: 在代码中, 我们使用 next_x, next_y, next_lie 等常数数组预先保存了长方体沿四个方向滚动的变化情况, 避免了使用大量 if 语句造成的混乱。这是广搜程序实现中的一个常见技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct rec { int x, y, lie; };  // 状态
char s[510][510];  // 地图
rec st, ed;  // 起始状态和目标状态
int n, m, d[510][510][3];  // 最少步数记录数组
queue<rec> q;  // 队列
bool valid(int x, int y) { return x>=1 && y>=1 && x<=n && y<=m; }
// 方向数组（方向0~3依次代表左右上下）
const int dx[4] = { 0,0,-1,1 }, dy[4] = { -1,1,0,0 };

void parse_st_ed() {  // 处理起点和终点
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'O') {
				ed.x = i, ed.y = j, ed.lie = 0, s[i][j] = '.';
			}
			else if (s[i][j] == 'X') {
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (valid(x, y) && s[x][y] == 'X') {
						st.x = min(i,x), st.y = min(j,y), st.lie = k<2?1:2;
						s[i][j] = s[x][y] = '.';
						break;
					}
				}
				if (s[i][j] == 'X') {
					st.x = i, st.y = j, st.lie = 0;
				}
			}
}

bool valid(rec next) {  // 滚动是否合法
	if (!valid(next.x, next.y)) return 0;
	if (s[next.x][next.y] == '#') return 0;
	if (next.lie == 0 && s[next.x][next.y] != '.') return 0;
	if (next.lie == 1 && s[next.x][next.y + 1] == '#') return 0;
	if (next.lie == 2 && s[next.x + 1][next.y] == '#') return 0;
	return 1;
}

// next_x[i][j]表示在lie=i时朝方向j滚动后x的变化情况
const int next_x[3][4] = { { 0,0,-2,1 },{ 0,0,-1,1 },{ 0,0,-1,2 } };
// next_y[i][j]表示在lie=i时朝方向j滚动后y的变化情况
const int next_y[3][4] = { { -2,1,0,0 },{ -1,2,0,0 },{ -1,1,0,0 } };
// next_lie[i][j]表示在lie=i时朝方向j滚动后lie的新值
const int next_lie[3][4] = { { 1,1,2,2 },{ 0,0,1,1 },{ 2,2,0,0 } };

int bfs() {  // 广搜
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int k = 0; k < 3; k++) d[i][j][k] = -1;
	while (q.size()) q.pop();
	d[st.x][st.y][st.lie] = 0;
	q.push(st);
	while (q.size()) {
		rec now = q.front(); q.pop();  // 取出队头
		for (int i = 0; i < 4; i++) {  // 向4个方向滚动
			rec next;
			next.x = now.x + next_x[now.lie][i];
			next.y = now.y + next_y[now.lie][i];
			next.lie = next_lie[now.lie][i];
			if (!valid(next)) continue;
			if (d[next.x][next.y][next.lie] == -1) {  // 尚未访问过
				d[next.x][next.y][next.lie] = d[now.x][now.y][now.lie]+1;
				q.push(next);
				if (next.x == ed.x && next.y == ed.y && next.lie == ed.lie)
					return d[next.x][next.y][next.lie];  // 到达目标
			}
		}
	}
	return -1;  // 无解
}

int main() {
	while (cin >> n >> m && n) {
		for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
		parse_st_ed();
		int ans = bfs();
		if (ans == -1) puts("Impossible"); else cout << ans << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct poi{
	int x,y,z;
	poi(){}
	poi(int x_,int y_,int z_) {x=x_,y=y_,z=z_;}
};
//0:立着，1:竖着躺，上半部分在(x,y)，2:横着躺，左半部分(x,y) 
const int dx[3][4]={{-2,0,1,0},{-1,0,2,0},{-1,0,1,0}};
const int dy[3][4]={{0,-2,0,1},{0,-1,0,1},{0,-1,0,2}};
const int dz[3][4]={{1,2,1,2},{0,1,0,1},{2,0,2,0}};
char a[510][510];
int n,m;
int d[510][510][3];
queue<poi> q;

bool in(int x,int y) {
	return x>=1&&x<=n&&y>=1&&y<=m;
}

bool valid(int x,int y,int z) {
	if(!in(x,y)||a[x][y]=='#') return 0;
	if(z==1&&(!in(x+1,y)||a[x+1][y]=='#')) return 0;
	if(z==2&&(!in(x,y+1)||a[x][y+1]=='#')) return 0;
	if(z==0&&a[x][y]=='E') return 0;
	return 1;
}

int bfs(int sx,int sy,int sz,int ex,int ey) {
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<3;k++)
				d[i][j][k]=-1;
	d[sx][sy][sz]=0;
	while(q.size()) q.pop();
	q.push(poi(sx,sy,sz));
	while(q.size()) {
		poi now=q.front(); q.pop();
		//cout<<now.x<<' '<<now.y<<' '<<now.z<<endl;
		for(int i=0;i<4;i++) {
			poi next=poi(now.x+dx[now.z][i],now.y+dy[now.z][i],dz[now.z][i]);
			if(!valid(next.x,next.y,next.z)) continue;
			if(d[next.x][next.y][next.z]==-1) {
				d[next.x][next.y][next.z]=d[now.x][now.y][now.z]+1;
				q.push(next);
				if(next.x==ex&&next.y==ey&&next.z==0) return d[next.x][next.y][next.z];
			}
		}
	}
	return -1;
}
// +1 两段性、单调性，第一次终点入队时，最优解 

int main() {
	while(cin>>n>>m&&n) {
		for(int i=1;i<=n;i++)
			scanf("%s",a[i]+1);
		int sx,sy,sz,ex,ey;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(a[i][j]=='X') {
					sx=i,sy=j,sz=0,a[i][j]='.';
					if(i<n&&a[i+1][j]=='X') sz=1,a[i+1][j]='.';
					if(j<m&&a[i][j+1]=='X') sz=2,a[i][j+1]='.';
				}
				else if(a[i][j]=='O') ex=i,ey=j,a[i][j]='.';
		int ans=bfs(sx,sy,sz,ex,ey);
		if(ans==-1) puts("Impossible"); else cout<<ans<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct P {
	int x, y, z;
} st, ed;
const int N = 506;
char s[N][N];
int n, m, d[N][N][3];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int nx[3][4] = {{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
int ny[3][4] = {{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
int nz[3][4] = {{1,1,2,2},{0,0,1,1},{2,2,0,0}};
queue<P> q;

bool pd(int x, int y) {
	return x >= 1 && y >= 1 && x <= n && y <= m;
}

bool pd(P p) {
	if (!pd(p.x, p.y)) return 0;
	if (s[p.x][p.y] == '#') return 0;
	if (p.z == 0 && s[p.x][p.y] != '.') return 0;
	if (p.z == 1 && s[p.x][p.y+1] == '#') return 0;
	if (p.z == 2 && s[p.x+1][p.y] == '#') return 0;
	return 1;
}

int bfs() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int k = 0; k < 3; k++)
				d[i][j][k] = -1;
	queue<P> empty;
	swap(q, empty);
	d[st.x][st.y][st.z] = 0;
	q.push(st);
	while (q.size()) {
		P now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			P p;
			p.x = now.x + nx[now.z][i];
			p.y = now.y + ny[now.z][i];
			p.z = nz[now.z][i];
			if (!pd(p)) continue;
			if (d[p.x][p.y][p.z] == -1) {
				d[p.x][p.y][p.z] = d[now.x][now.y][now.z] + 1;
				q.push(p);
				if (p.x == ed.x && p.y == ed.y && p.z == ed.z)
					return d[p.x][p.y][p.z];
			}
		}
	}
	return -1;
}

int main() {
	while (cin >> n >> m && n) {
		for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (s[i][j] == 'O') {
					ed.x = i;
					ed.y = j;
					ed.z = 0;
					s[i][j] = '.';
				} else if (s[i][j] == 'X') {
					for (int k = 0; k < 4; k++) {
						int x = i + dx[k], y = j + dy[k];
						if (pd(x, y) && s[x][y] == 'X') {
							st.x = min(i, x);
							st.y = min(j, y);
							st.z = k < 2 ? 1 : 2;
							s[i][j] = s[x][y] = '.';
							break;
						}
					}
					if (s[i][j] == 'X') {
						st.x = i;
						st.y = j;
						st.z = 0;
					}
				}
		int ans = bfs();
		if (ans == -1) puts("Impossible");
		else cout << ans << endl;
	}
	return 0;
}

Solution

173. 矩阵距离（多源flood fill）

题目描述

给定一个 NN 行 MM 列的 0101 矩阵 AA，A[i][j]A[i][j] 与 A[k][l]A[k][l] 之间的曼哈顿距离定义为：

dist(A[i][j],A[k][l])=∣i−k∣+∣j−l∣dist(A[i][j],A[k][l])=|i-k|+|j-l|

输出一个 NN 行 MM 列的整数矩阵 BB，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1⁡dist(A[i][j],A[x][y])B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}⁡{dist(A[i][j],A[x][y])}

输入格式

第一行两个整数 N,MN,M。

接下来一个 NN 行 MM 列的 0101 矩阵，数字之间没有空格。

输出格式

一个 NN 行 MM 列的矩阵 BB，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤10001 \le N,M \le 1000

输入样例：

1
2
3
4
3 4
0001
0011
0110

输出样例：

1
2
3
3 2 1 0
2 1 0 0
1 0 0 1

算法分析

先来思考这样一个问题: 给定一个 N∗MN * M 的 01 矩阵和一个起点 (0(0 表示可通行点, 1 表示禁止点), 每一步可以向上、下、左、右四个方向之一移动 1 单位距离, 求从起点出发能够到达哪些位置, 以及到达每个位置的最少步数。这是广度优先搜索的最基本应用, 我们也称 BFS 求解该问题的算法为 flood-fill, 就好像在起点倒水, 看能覆盖多大的一片区域。

本题可以看作一道有多个起始状态的 flood-fill 问题。我们把矩阵 AA 中每一个 1 都看作起点, 整个矩阵的所有位置都可以通行, 对于每个位置, 在从任何一个起点出发都可以的情况下, 求到达该位置所需要的最少步数 (也就是距离该位置最近的起点的距离)。

在这种具有多个等价的起始状态的问题中, 我们只需要在 BFS 开始之前把这些起始状态全部插入队列。根据 BFS 逐层搜索的性质, BFS 的过程就相当于每个起点先扩展 1 层, 再扩展 2 层, 3 层, 依此类推。所以当每个位置 (x,y)(x, y) 第一次被访问时, 就相当于距离它最近的那个起点扩展到了它, 此时从那个起点到 (x,y)(x, y) 经历的步数就是最短距离 B[x][y]B[x][y] 。如下图所示:

编写广搜代码时, 再次提醒读者注意地图边界的检查、记录数组 dd 的初始化, 并用方向常数数组 dx,dyd x, d y 避免多个 if 分支, 用 0∼30 \sim 3 代指上、下、左、右四个方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
char s[1020][1020];
int d[1020][1020], n, m;
queue<pair<int, int>> q;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
	memset(d, -1, sizeof(d));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '1') q.push(make_pair(i, j)), d[i][j] = 0;
	while (q.size()) {
		pair<int, int> now = q.front();
		q.pop();
		for (int k = 0; k < 4; k++) {
			pair<int, int> next(now.first + dx[k], now.second + dy[k]);
			if (next.first<1 || next.second<1 || next.first>n || next.second>m) continue;
			if (d[next.first][next.second] == -1) {
				d[next.first][next.second] = d[now.first][now.second] + 1;
				q.push(next);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) printf("%d ", d[i][j]);
		puts("");
	}
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int N = 1010, M = N * N;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct pos{
  int x, y;
};

int n, m;
char g[N][N];
int dist[N][N];
pos q[M];

bool check(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= m;
}

bool vis(int x, int y) {
  return dist[x][y] != -1;
}

void bfs() {
  int hh = 0, tt = -1;
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= m; ++j)
      if (g[i][j] == '1') {
        q[++tt] = {i, j};
        dist[i][j] = 0;
      }
      
  while (hh <= tt) {
    auto now = q[hh++];
    for (int i = 0; i < 4; ++i) {
      int x = now.x + dx[i], y = now.y + dy[i];
      if (check(x, y) && dist[x][y] == -1) {
        q[++tt] = {x, y};
        dist[x][y] = dist[now.x][now.y] + 1;
      }
    }
  }
} 

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> g[i] + 1;//输入没有空格，用字符串读入

  memset(dist, -1, sizeof dist);
  
  bfs();
  
  for(int i = 1; i <= n; ++i){
    for (int j = 1; j <= m; ++j) cout << dist[i][j] << " ";
    cout << endl;
  }
}

174. 推箱子（双重BFS）

题目描述

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把 11 个箱子到目的地。

给定一张 NN 行 MM 列的地图，用字符 . 表示空地，字符 # 表示墙，字符 S 表示人的起始位置，字符 B 表示箱子的起始位置，字符 T 表示箱子的目标位置。

求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。

方案中使用大写的 EWSN（东西南北）表示箱子的移动，使用小写的 ewsn（东西南北）表示人的移动。

输入格式

输入包含多个测试用例。

对于每个测试用例，第一行包括两个整数 N，MN，M。

接下来 NN 行，每行包括 MM 个字符，用以描绘整个 NN 行 MM 列的地图。

当样例为 N=0，M=0N=0，M=0 时，表示输入终止，且该样例无需处理。

输出格式

对于每个测试用例，第一行输出 Maze #+测试用例的序号。

第二行输入一个字符串，表示推箱子的总体移动过程，若无解，则输出 Impossible.。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求，则按照 N、S、W、E 的顺序优先选择箱子的移动方向（即先上下推，再左右推）。

在此前提下，再按照 n、s、w、e 的顺序优先选择人的移动方向（即先上下动，再左右动）。

数据范围

1≤N,M≤201 \le N,M \le 20

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

输出样例：

1
2
3
4
5
6
7
8
9
10
11
Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

算法分析

在这道题目中，箱子和人都会移动，并且二者的移动可能不是同步的。一个直接的想法是把人和箱子的位置一起组成一个状态, 这样的状态是一个四元组, 规模是 O(N2M2)\mathrm{O}\left(N^{2} M^{2}\right) 。如果直接使用这个算法进行广搜, 会出现一些问题:

  1. 题目要求先保证箱子移动的总步数 step_boxstep\_box 最少, 再保证人移动的总步数 step_manstep\_man 最少。根据我们之前提到过的广搜的性质, 应该让队列中的状态对应的步数二元组 (step_box,step_man)(step\_box, step\_man) 保持单调性 (即队列中的状态满足第一关键字 step_boxstep\_box 递增, 当 step_boxstep\_box 相同时第二关键字 step_manstep\_man 递增)。
    然而, 在对每个状态进行扩展时, 有的时候箱子和人移动的步数都会增加, 有的时候只有人移动的步数会增加。如果像往常一样简单地把新状态放在队尾, 就可能会破坏队列中的状态对应 “步数二元组” 的单调性。

  2. 在队列状态不满足步数单调性时, 每个状态只访问一次的广搜会求出错误的答 案。我们在 “广搜变形” 中会提到几种解决方案, 比如使用迭代的思想多次更新一个状态, 或者改用优先队列进行广搜。然而这些方案都会进一步增加算法的时间复杂度 (至少增加一个 log⁡\log )。本题每个测试点包含很多组数据, 上述算法都会导致超时。

进一步分析本问题, 我们可以发现, 在每次箱子移动后, 人一定位于箱子之前处于的位置上。于是, 我们可以把每次箱子刚刚移动后, 箱子与人的位置打包构成一个状态, 记为 (x,y,dir)(x, y, d i r), 其中 (x,y)(x, y) 表示箱子处于第 xx 行第 yy 列, dird i r 是一个 0∼30 \sim 3 之间的整数值, 指示人处于箱子旁边四个位置中的哪一个。如果我们像上一道题目一样使用方向常数数组 dxd x 和 dyd y, 那么人的位置就可以表示为 (x−dx[dir],y−dy[dir])(x-d x[d i r], y-d y[d i r]) 。

另外, 我们使用数组 f−box[x][y][dir]f_{-} b o x[x][y][d i r] 和 f−man[x][y][dir]f_{-} m a n[x][y][d i r] 分别记录每个状态下
箱子和人已经移动的步数。

对于任意一个状态 (x,y,dir)(x, y, d i r), 都可能有四个分支, 代表箱子可能向四个方向移动。我们仍使用方向常数数组, 然后枚举方向 k=0∼3k=0 \sim 3, 则扩展到的下一个状态就是 (x+dx[k],y+dy[k],k)(x+d x[k], y+d y[k], k), 移动的方式是:

  1. 箱子在 (x,y)(x, y) 处不动, 人用尽量少的步数从起点 (x−dx[dir],y−dy[dir])(x-d x[d i r], y-d y[d i r]) 移动到终点 (x−dx[k],y−dy[k])(x-d x[k], y-d y[k]), 并且途中不能经过 (x,y)(x, y) 。
  2. 人沿着 kk 方向推一次箱子, 箱子移动到 (x+dx[k],y+dy[k])(x+d x[k], y+d y[k]), 人移动到 (x,y)(x, y) 。

此后, 我们把新状态 (x+dx[k],y+dy[k],k)(x+d x[k], y+d y[k], k) 入队, 并存储新状态对应的 f−boxf_{-} b o x 与 f−man⁡f_{-} \operatorname{man} 的值。

这是一个双重 BFS 算法。从整体上看, 算法在对每次箱子移动后的 “箱子与旁边的人” 这个合体进行 BFS。而在这个 BFS 的每一次状态扩展时, 我们再用 “对人进行的另一个 BFS” 求出人在两个位置之间移动的最少步数。

我们在程序设计时常常讲究代码的 “模块性”。如果我们把 (x,y,dir)(x, y, d i r) 这个状态扩展时发生的移动写成一个函数 expand, 该函数返回箱子和人移动的步数, 那么算法本身其实就是一个普普通通的 BFS, 只不过它每一步扩展时使用的计算函数 expand 内, 恰好又需要使用 BFS 而已。

除了代码编写的 “模块性”, 在理解、设计算法时, 也要时刻秉承 “模块化” 的思想。整个问题有一个大的解决框架, 框架的每个细节可能又是一个 “小问题”, 小问题的解决框架的细节可能还有其他更小的 “子问题”, 就像一棵树一样逐层深入。读者在设计其中每个问题的算法时, 要专注于整体框架, 不妨假设细节部分的 “小问题” 已经处理完毕, 争取把每个框架都转化成我们学过的类似 “模型”。这样的话, 无论多么复杂的问题都会迎刃而解了。

最后, 我们还需要讨论上述算法的正确性。对于状态 (x,y,dir)(x, y, d i r) 进行的外层 BFS, 在每次状态扩展的移动过程中, 箱子一定移动了 1 步, 人可能移动了若干步, 并且状态中的 dir⁡\operatorname{dir} 相当于移动的方向 (还相当于分支来源)。所以, 在第二次访问某个状态时, 箱子移动的步数一定比第一次多 (请读者仔细思考为什么带有 dir\mathrm{dir} 的状态就满足这个性质)。因此, 每个状态 (x,y,dir)(x, y, d i r) 只访问一次的这个双重 BFS 算法就可以求出最优解, 其状态规模为 O(NM)O(N M), 每次扩展最多花 O(NM)O(N M) 的时间进行内层 BFS, 总体时间复杂度不超过 O(N2M2)\mathrm{O}\left(N^{2} M^{2}\right) 。

本题还要求输出一种具体方案, 我们可以额外用数组记录最终的每个 f−boxf_{-} b o x 与 f−man⁡f_{-} \operatorname{man} 值是从上一步的哪个状态更新而来的 (也就是记录搜索树上的父节点), 在求出最优解后向前逆推得到箱子的运动轨迹。最后我们按照箱子的运动轨迹, 在相邻的两次移动之间重新对人进行 BFS, 组合起来即可得到最终的方案。这种记录和逆推的方法是各种搜索、动态规划题目输出方案的常用做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 26, INF = 0x3f3f3f3f;
char A[4] = {'N','S','W','E'};
char a[4] = {'n','s','w','e'};
int r, c, num = 0;
int d[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
char s[N][N];
string tmp;
struct P {
	int x, y, px, py;
	string ans;
};

bool pd(int x, int y) {
	return x > 0 && x <= r && y > 0 && y <= c && s[x][y] != '#';
}

bool bfs2(P p1, P p2) {
	tmp = "";
	P st;
	st.x = p1.px;
	st.y = p1.py;
	st.ans = "";
	queue<P> q;
	q.push(st);
	bool v[N][N];
	memset(v, 0, sizeof(v));
	while (q.size()) {
		P now = q.front(), nxt;
		q.pop();
		if (now.x == p1.x && now.y == p1.y) {
			tmp = now.ans;
			return 1;
		}
		for (int i = 0; i < 4; i++) {
			nxt = now;
			nxt.x = now.x + d[i][0];
			nxt.y = now.y + d[i][1];
			if (!pd(nxt.x, nxt.y)) continue;
			if (nxt.x == p2.x && nxt.y == p2.y) continue;
			if (v[nxt.x][nxt.y]) continue;
			v[nxt.x][nxt.y] = 1;
			nxt.ans = now.ans + a[i];
			q.push(nxt);
		}
	}
	return 0;
}

string bfs1() {
	P st;
	st.x = st.y = st.px = st.py = -1;
	st.ans = "";
	for (int i = 1; i <= r && (st.x == -1 || st.px == -1); i++)
		for (int j = 1; j <= c && (st.x == -1 || st.px == -1); j++)
			if (s[i][j] == 'B') {
				st.x = i;
				st.y = j;
				s[i][j] = '.';
			} else if (s[i][j] == 'S') {
				st.px = i;
				st.py = j;
				s[i][j] = '.';
			}
	queue<P> q;
	q.push(st);
	bool v[N][N][4];
	memset(v, 0, sizeof(v));
	string ans = "Impossible.";
	unsigned int cntans = INF, cnt = INF;
	while (q.size()) {
		P prv, now = q.front(), nxt;
		q.pop();
		if (s[now.x][now.y] == 'T') {
			unsigned int cntnow = 0;
			for (unsigned int i = 0; i < now.ans.length(); i++)
				if (now.ans[i] >= 'A' && now.ans[i] <= 'Z') ++cntnow;
			if (cntnow < cntans || (cntnow == cntans && now.ans.length() < cnt)) {
				ans = now.ans;
				cntans = cntnow;
				cnt = now.ans.length();
			}
			continue;
		}
		for (int i = 0; i < 4; i++) {
			nxt = now;
			nxt.x = now.x + d[i][0];
			nxt.y = now.y + d[i][1];
			if (!pd(nxt.x, nxt.y)) continue;
			if (v[nxt.x][nxt.y][i]) continue;
			prv = now;
			if (i == 3) prv.y = now.y - 1;
			else if (i == 2) prv.y = now.y + 1;
			else if (i == 1) prv.x = now.x - 1;
			else prv.x = now.x + 1;
			if (!bfs2(prv, now)) continue;
			v[nxt.x][nxt.y][i] = 1;
			nxt.ans = now.ans + tmp;
			nxt.ans = nxt.ans + A[i];
			nxt.px = now.x;
			nxt.py = now.y;
			q.push(nxt);
		}
	}
	return ans;
}

void Pushing_Boxes() {
	for (int i = 1; i <= r; i++) cin >> (s[i] + 1);
	cout << "Maze #" << ++num << endl << bfs1() << endl << endl;
}

int main() {
	while (cin >> r >> c && r && c) Pushing_Boxes();
	return 0;
}

Solution

Flood Fill

1097. 池塘计数（连通块个数）

题目描述

农夫约翰有一片 N∗MN*M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式

第一行包含两个整数 NN 和 MM。

接下来 NN 行，每行包含 MM 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式

输出一个整数，表示池塘数目。

数据范围

1≤N,M≤10001 \le N,M \le 1000

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例：

1
3

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;

const int N = 1010;
const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

struct pos {
  int x, y;
};

int n, m;
char g[N][N];
bool vis[N][N];
pos q[N * N];

bool check(pos ver) {
  return ver.x >= 1 && ver.x <= n && ver.y >= 1 && ver.y <= m;
}

void bfs(pos u) {
  int hh = 0, tt = -1;
  q[++tt] = u;
  vis[u.x][u.y] = true;
  while (hh <= tt) {
    pos now = q[hh++];
    for (int i = 0; i < 8; ++i) {
      pos ver = {now.x + dx[i], now.y + dy[i]};
      if (check(ver) && g[ver.x][ver.y] == 'W' && !vis[ver.x][ver.y]) {
        q[++tt] = ver;
        vis[ver.x][ver.y] = true;
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= m; ++j) cin >> g[i][j];

  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (!vis[i][j] && g[i][j] == 'W') {
        bfs({i, j});
        ++cnt;
      }
    }
  }

  cout << cnt;
}

1098. 城堡问题(连通块面积)

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1   2   3   4   5   6   7  
  #############################
1 #   |   #   |   #   |   |   #
  #####---#####---#---#####---#
2 #   #   |   #   #   #   #   #
  #---#####---#####---#####---#
3 #   |   |   #   #   #   #   #
  #---#########---#####---#---#
4 #   #   |   |   |   |   #   #
  #############################
          (图 1)

  #  = Wall   
  |  = No wall
  -  = No wall

  方向：上北下南左西右东。

图1是一个城堡的地形图。

请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m∗nm*n个方格区域，每个方格区域可以有0~4面墙。

注意：墙体厚度忽略不计。

输入格式

第一行包含两个整数 mm 和 nn，分别表示城堡南北方向的长度和东西方向的长度。

接下来 mm 行，每行包含 nn 个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 PP 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，PP 为该方块包含墙的数字之和。

例如，如果一个方块的 PP 为3，则 3 = 1 + 2，该方块包含西墙和北墙。

城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。

输入的数据保证城堡至少有两个房间。

输出格式

共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。

数据范围

1≤m,n≤501 \le m,n \le 50,
0≤P≤150 \le P \le 15

输入样例：

1
2
3
4
5
4 7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13

输出样例：

1
2
5
9

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};

struct pos{
  int x, y;
};

int n, m;
int g[N][N];
bool vis[N][N];
pos q[N * N];

bool check(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= m;
}

int bfs(pos u) {
  int hh = 0, tt = -1;
  int area = 0;
  q[++tt] = u;
  vis[u.x][u.y] = true;
  while (hh <= tt) {
    auto now = q[hh++];
    for (int i = 0; i < 4; ++i) {
      if (g[now.x][now.y] >> i & 1) continue;
      int x = now.x + dx[i], y = now.y + dy[i];
      if (!check(x, y) || vis[x][y]) continue;
      q[++tt] = {x, y};
      vis[x][y] = true;
      ++area;
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= m; ++j) cin >> g[i][j];
    
  int cnt = 0, area = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (vis[i][j]) continue;
      area = max(area, bfs({i, j}));
      ++cnt;
    }
  }
	
  cout << cnt << endl << area;
}

1106. 山峰和山谷

题目描述

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×nn \times n 的网格，每个格子 (i,j)(i,j) 的高度 w(i,j)w(i,j) 是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j)(i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)(i-1, j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)。

我们定义一个格子的集合 SS 为山峰（山谷）当且仅当：

  1. SS 的所有格子都有相同的高度。
  2. SS 的所有格子都连通。
  3. 对于 ss 属于 SS，与 ss 相邻的 s’s’ 不属于 SS，都有 ws>ws’w_s > w_{s’}（山峰），或者 ws<ws’w_s < w_{s’}（山谷）。
  4. 如果周围不存在相邻区域，则同时将其视为山峰和山谷。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式

第一行包含一个正整数 nn，表示地图的大小。

接下来一个 n×nn \times n 的矩阵，表示地图上每个格子的高度 ww。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

1≤n≤10001 \le n \le 1000,
0≤w≤1090 \le w \le 10^9

输入样例1：

1
2
3
4
5
6
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

输出样例1：

1
2 1

输入样例2：

1
2
3
4
5
6
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

输出样例2：

1
3 3

样例解释

样例1：

样例2：

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;

const int N = 1010;

struct pos{
  int x, y;
};

int n;
int h[N][N];
pos q[N * N];
bool vis[N][N];

bool check(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= n;
}

void bfs(pos u, bool &hasHigher, bool &hasLower) {
  int hh = 0, tt = -1;
  q[++tt] = u;
  vis[u.x][u.y] = true;
  while (hh <= tt) {
    auto now = q[hh++];
    for (int x = now.x - 1; x <= now.x + 1; ++x) {
      for (int y = now.y - 1; y <= now.y + 1; ++y) {
        if (x == now.x && y == now.y) continue;
        if (!check(x, y)) continue;
        if (h[x][y] > h[u.x][u.y]) hasHigher = true;
        if (h[x][y] < h[u.x][u.y]) hasLower = true;
        if (h[x][y] == h[u.x][u.y] && !vis[x][y]) {
          q[++tt] = {x, y};
          vis[x][y] = true;
        }
      }
    }
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= n; ++j) cin >> h[i][j];
  
  int peak = 0, valley = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (vis[i][j]) continue;
      bool hasHigher = false, hasLower = false;
      bfs({i, j}, hasHigher, hasLower);
      if (!hasHigher) ++peak;
      if (!hasLower) ++valley;
    }
  }
  
  cout << peak << " " << valley;
}

BFS最短路模型

1076. 迷宫问题

题目描述

给定一个 n×nn \times n 的二维数组，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maze[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,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 n。

接下来 nn 行，每行包含 nn 个整数 0 或 1，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)(0,0)，右下角坐标为 (n−1,n−1)(n-1,n-1)。

数据范围

0≤n≤10000 \le n \le 1000

输入样例：

1
2
3
4
5
6
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

输出样例：

1
2
3
4
5
6
7
8
9
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;

const int N = 1010;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct pos{ 
  int x, y;
};
  
int n;
int g[N][N];
pos q[N * N];
bool vis[N][N];
pos prevPos[N][N];//存储前一个点

bool check(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < n;
}

void bfs(pos u) {
  int hh = 0, tt = -1;
  q[++tt] = u;
  vis[u.x][u.y] = true;
  while (hh <= tt) {
    pos now = q[hh++];
    for (int i = 0; i < 4; ++i) {
      int x = now.x + dx[i], y = now.y + dy[i];
      if (check(x, y) && g[x][y] == 0 && !vis[x][y]) {
        q[++tt] = {x, y};
        prevPos[x][y] = now;
        vis[x][y] = true;
      }
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) 
    for (int j = 0; j < n; ++j) cin >> g[i][j];
  
  //路径输出是倒序的，故可以从终点开始BFS，倒序输出路径点，即为从起点到终点的最短路径
  bfs({n - 1, n - 1});
  
  pos ed = {0, 0};
  
  while (true) {
    cout << ed.x << " " << ed.y << endl;
    if (ed.x == n - 1 && ed.y == n - 1) break;
    ed = prevPos[ed.x][ed.y];
  }
  
}

188. 武士风度的牛（日字型）

题目描述

农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，yx，y 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。

The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。

这里有一个地图的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
11 | . . . . . . . . . .
10 | . . . . * . . . . . 
 9 | . . . . . . . . . . 
 8 | . . . * . * . . . . 
 7 | . . . . . . . * . . 
 6 | . . * . . * . . . H 
 5 | * . . . . . . . . . 
 4 | . . . * . . . * . . 
 3 | . K . . . . . . . . 
 2 | . . . * . . . . . * 
 1 | . . * . . . . * . . 
 0 ----------------------
                       1 
   0 1 2 3 4 5 6 7 8 9 0

The Knight 可以按照下图中的 A,B,C,D…A,B,C,D… 这条路径用 55 次跳到草的地方（有可能其它路线的长度也是 55）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
11 | . . . . . . . . . .
10 | . . . . * . . . . .
 9 | . . . . . . . . . .
 8 | . . . * . * . . . .
 7 | . . . . . . . * . .
 6 | . . * . . * . . . F<
 5 | * . B . . . . . . .
 4 | . . . * C . . * E .
 3 | .>A . . . . D . . .
 2 | . . . * . . . . . *
 1 | . . * . . . . * . .
 0 ----------------------
                       1
   0 1 2 3 4 5 6 7 8 9 0

注意： 数据保证一定有解。

输入格式

第 11 行： 两个数，表示农场的列数 CC 和行数 RR。

第 2..R+12..R+1 行: 每行一个由 CC 个字符组成的字符串，共同描绘出牧场地图。

输出格式

一个整数，表示跳跃的最小次数。

数据范围

1≤R,C≤1501 \le R,C \le 150

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

输出样例：

1
5

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 160, M = N * N;
const int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

struct pos{
  int x, y;
};

int n, m;
char g[N][N];
pos q[M];
bool vis[N][N];
int dist[N][N];

bool check(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= m;
}

int bfs(pos u){
  int hh = 0, tt = -1;
  q[++tt] = u;
  vis[u.x][u.y] = true;
  while (hh <= tt) {
    auto now = q[hh++];
    for (int i = 0; i < 8; ++i) {
      int x = now.x + dx[i], y = now.y + dy[i];
      if (!check(x, y) || vis[x][y] || g[x][y] == '*') continue;
      if (g[x][y] == 'H') return dist[now.x][now.y] + 1;
      q[++tt] = {x, y};
      vis[x][y] = true;
      dist[x][y] = dist[now.x][now.y] + 1;
    }
  }
  return -1;
}

int main() {
  cin >> m >> n;
  
  pos st;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> g[i][j];
      if (g[i][j] == 'K') st = {i, j};
    }
  }
  
  cout << bfs(st); 
}

1100. 抓住那头牛

题目描述

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 NN，牛位于点 KK。

农夫有两种移动方式：

  1. 从 XX 移动到 X−1X-1 或 X+1X+1，每次移动花费一分钟
  2. 从 XX 移动到 2∗X2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

0≤N,K≤1050 \le N,K \le 10^5

输入样例：

1
5 17

输出样例：

1
4

算法分析

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <queue>
using namespace std;

const int N = 1e5 + 10;

int n, k;
bool vis[N];
int dist[N];

bool check(int pos) {
  return pos >= 0 && pos <= N;
}

int bfs(int u) {
  queue<int> q;
  q.push(u);
  vis[u] = true;
  while (q.size()) {
    int now = q.front(); q.pop();
    if (now == k) return dist[k];
    int a[3] = {now + 1, now - 1, now * 2};
    for (int i = 0; i < 3; ++i) {
      int next = a[i];
      if (check(next) && !vis[next]) {
        q.push(next);
        vis[next] = true;
        dist[next] = dist[now] + 1;
      }
    }
  }
  return -1;
}

int main() {
  cin >> n >> k;
  
  cout << bfs(n);
}

走地图 / 状态最小步数

常用字符串表示状态，哈希表存储状态

1107. 魔板

题目描述

Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。

这是一张有 88 个大小相同的格子的魔板：

1
2
1 2 3 4
8 7 6 5

我们知道魔板的每一个方格都有一种颜色。

这 88 种颜色用前 88 个正整数来表示。

可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。

对于上图的魔板状态，我们用序列 (1,2,3,4,5,6,7,8)(1,2,3,4,5,6,7,8) 来表示，这是基本状态。

这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：

A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。

下面是对基本状态进行操作的示范：

A：

1
2
8 7 6 5
1 2 3 4

B：

1
2
4 1 2 3
5 8 7 6

C：

1
2
1 7 2 4
8 6 3 5

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。

注意：数据保证一定有解。

输入格式

输入仅一行，包括 88 个整数，用空格分开，表示目标状态。

输出格式

输出文件的第一行包括一个整数，表示最短操作序列的长度。

如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。

数据范围

输入数据中的所有数字均为 11 到 88 之间的整数。

输入样例：

1
2 6 8 4 5 7 3 1

输出样例：

1
2
7
BCABCCB

算法分析

按A、B、C顺序枚举操作，即可以得到最小字典序

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<string, pair<int,string>> dist;

string A(string s) {
  reverse(s.begin(), s.end());
  return s;
}

string B(string s) {
  return s[3] + s.substr(0,3) + s.substr(5,3) + s[4];
  return s;
}

string C(string s) {
  auto t = s[1];
  s[1] = s[6];
  s[6] = s[5];
  s[5] = s[2];
  s[2] = t;
  return s;
}

bool vis(string &s) {
  return dist.count(s);
}

void bfs(string st, string ed) {
  queue<string> q;
  q.push(st);
  dist[st].first = 0;
  while (q.size()) {
    auto now = q.front(); q.pop();
    
    string next[3];
    next[0] = A(now);
    next[1] = B(now);
    next[2] = C(now);
    
    for (int i = 0; i < 3; ++i) {
      if (!vis(next[i])) {
        dist[next[i]].first = dist[now].first + 1;
        char op = i + 'A';
        dist[next[i]].second = dist[now].second + op;
        if (next[i] == ed) return;
        q.push(next[i]);
      }      
    }
  }
}


int main() {
  string st = "12345678", ed;
  for (int i = 1, c; i <= 8; ++i) {
    cin >> c;
    ed += c + '0';
  }

  bfs(st, ed);
  
  cout << dist[ed].first << endl;
  if (dist[ed].first) {
    cout << dist[ed].second;
  }
}