（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
难度：简单
时/空限制：1s / 64MB
总通过数：28223
总尝试数：49805
来源：模板题
算法标签
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
PII Prev[N][N];
int bfs()
{
queue<PII> q;
memset(d, -1, sizeof d);
d[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 ++ )
{
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] = d[t.first][t.second] + 1;
Prev[x][y] = t;
q.push({x, y});
}
}
}
int x = n - 1, y = m - 1;
while(x || y)//有一个不d等于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;
}
迷宫问题（从入口到出口打印路径）
给定一个 n×n 的二维数组，如下所示：
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。
接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。
输出格式
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
输入样例：
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
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int g[N][N], d[N][N];
PII Prev[N][N];
void bfs()
{
queue<PII> q;
memset(d, -1, sizeof d);
d[n-1][n-1] = 0;
q.push({n-1, n-1});
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 ++ )
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n && 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 main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &g[i][j]);
bfs() ;
PII end(0, 0);
while (true)
{
printf("%d %d\n", end.x, end.y);
if (end.x == n - 1 && end.y == n - 1) break;
end = Prev[end.x][end.y];
}
return 0;
}
(2)wyh的迷宫
链接：https://ac.nowcoder.com/acm/problem/15434
来源：牛客网
题目描述
给你一个n*m的迷宫，这个迷宫中有以下几个标识：
s代表起点
t代表终点
x代表障碍物
.代表空地
现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点
输出描述:
对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO
示例1
输入
复制
1
3 5
s…x
x…x
…tx
输出
复制
YES
代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N = 511;
typedef pair<int, int> PII;
char c[N][N];
int d[N][N];
int n, m;
int bfs(int x, int y, int a, int b)
{
queue<PII> q;
memset(d, -1, sizeof(d));
d[x][y] = 0;
q.push({x, y});
while(q.size())
{
PII t = q.front();
q.pop();
//cout << t.first <<" " << t.second << endl;
if(t.first == a && t.second == b) return 1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(int i = 0; i < 4; i++)
{
int DX = t.first + dx[i], DY = t.second + dy[i];
if(DX >= 0 && DX < n && DY >=0 && DY < m && c[DX][DY] != 'x' && d[DX][DY] == -1)
{
d[DX][DY] = d[t.first][t.second] + 1;
q.push({DX, DY});
}
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
int x, y;
int a, b;
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < m; j++)
{
cin >> c[i][j];
if(c[i][j] == 's')
{
x = i, y = j;
}
if(c[i][j] == 't')
{
a = i, b = j;
}
}
}
//cout << x << " " << y <<" " << a << " " << b << endl;
if(bfs(x, y, a, b)==1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
(3)池塘计数
农夫约翰有一片 N∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。
输出格式
输出一个整数，表示池塘数目。
数据范围
1≤N,M≤1000
输入样例：
10 12
W........WW.
.WWW.....WWW
....WW…WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出样例：
3
难度：简单
时/空限制：1s / 64MB
总通过数：6764
总尝试数：10905
来源：《信息学奥赛一本通》 , POJ2386
算法标签
代码：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 1010;
char g[N][N];
int n,m;
void bfs(int sx,int sy)
{
queue<PII> q;
q.push({sx,sy});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=t.x-1;i<=t.x+1;i++)
{
for(int j=t.y-1;j<=t.y+1;j++)
{
if(i<0||i>=n||j<0||j>=m)continue;
if (i == t.x && j == t.y) continue;
if(g[i][j]=='.')continue;
g[i][j]='.';
q.push({i,j});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
int cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'W')
{
bfs(i, j);
cnt ++ ;
}
cout<<cnt;
}
(4)城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####—#####—#—#####—#
2 # # | # # # # #
#—#####—#####—#####—#
3 # | | # # # # #
#—#########—#####—#—#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
方向：上北下南左西右东。
图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 m∗n个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。
输入格式
第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。
例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围
1≤m,n≤50,
0≤P≤15
输入样例：
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
输出样例：
5
9
代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 55;
bool st[N][N];
char g[N][N];
int n,m;
typedef pair<int,int> PII;
queue<PII> q;
int bfs(int sx,int sy)
{
q.push({sx,sy});
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
//循环中第一次i>>0位其实是看有没有南墙(因为南墙是所有数都为1),所以要从南方向的偏移量开始写
int res=0;
st[sx][sy]=true;
while(q.size())
{
auto t= q.front();
q.pop();
res++;
for(int i=0;i<4;i++)
{
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
if(st[x][y]) continue; //是被遍历过
if(g[t.first][t.second]>>i&1) continue; //分别判断该房间四周的墙
q.push({x,y});
st[x][y]=true;
}
}
return res;
}
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]);
}
}
int cnt=0,res=0; //cnt来存连通块的数量，res来存最大连通块
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!st[i][j]){
res=max(res,bfs(i,j));
cnt++;
}
}
}
printf("%d\n%d",cnt,res);
return 0;
}
(5)山峰和山谷
FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。
为了能够对旅程有一个安排，他想知道山峰和山谷的数量。
给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i,j) 的高度 w(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)。
我们定义一个格子的集合 S 为山峰（山谷）当且仅当：
S 的所有格子都有相同的高度。
S 的所有格子都连通。
对于 s 属于 S，与 s 相邻的 s′ 不属于 S，都有 ws>ws′（山峰），或者 ws<ws′（山谷）。
如果周围不存在相邻区域，则同时将其视为山峰和山谷。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。
输入格式
第一行包含一个正整数 n，表示地图的大小。
接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。
输出格式
共一行，包含两个整数，表示山峰和山谷的数量。
数据范围
1≤n≤1000,
0≤w≤109
输入样例1：
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：
2 1
输入样例2：
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：
3 3
样例解释
样例1：
1.png
样例2：
2.png
代码：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N];
bool st[N][N];
queue<PII> q;
int n;
void bfs(int sx, int sy, bool& has_higher, bool& has_lower)
{
q.push({sx,sy});
st[sx][sy]=true;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=t.first-1;i<=t.first+1;i++)
{
for(int j=t.second-1;j<=t.second+1;j++)
{
if(i==t.first&&j==t.second)continue;
if (i < 0 || i >= n || j < 0 || j >= n) continue;
if(g[i][j]!=g[t.first][t.second])
{
if(g[i][j]>g[t.first][t.second])
{
has_higher=true;
}
else
{
has_lower=true;
}
}
else if(!st[i][j])
{
q.push({i,j});
st[i][j]=true;
}
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
int peak=0; //山峰
int vally=0; //山谷
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(!st[i][j])
{
bool has_higher=false;
bool has_lower=false;
bfs(i,j,has_higher,has_lower);
if(!has_higher)peak++;
if(!has_lower)vally++;
}
}
}
printf("%d %d",peak,vally);
return 0;
}
(6)武士风度的牛
农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。
虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。
现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。
The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。
这里有一个地图的例子：
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… 这条路径用 5 次跳到草的地方（有可能其它路线的长度也是 5）：
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
注意： 数据保证一定有解。
输入格式
第 1 行： 两个数，表示农场的列数 C 和行数 R。
第 2..R+1 行: 每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。
输出格式
一个整数，表示跳跃的最小次数。
数据范围
1≤R,C≤150
输入样例：
10 11
..........
.........
..........
….....
.........
....…H
.........
……..
.K........
….....
......*..
输出样例：
5
难度：简单
时/空限制：1s / 64MB
总通过数：4565
总尝试数：8840
来源：《算法竞赛进阶指南》
算法标签
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 160;
int n, m;
char g[N][N];
int d[N][N];
queue<PII> q;
int bfs()
{
int sx, sy;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
if (g[i][j] == 'K')
{
sx = i, sy = j;
}
}
}
q.push({sx, sy});
memset(d, -1, sizeof d);
d[sx][sy] = 0;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 8; i ++ )
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '.' && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
if (g[x][y] == 'H'&& d[x][y] == -1) return d[t.first][t.second] + 1;
}
}
return -1;
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )cin>>g[i];
cout<<bfs();
return 0;
}
(7)抓住那头牛
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
输入格式
共一行，包含两个整数N和K。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
0≤N,K≤105
输入样例：
5 17
输出样例：
4
难度：简单
时/空限制：1s / 64MB
总通过数：4249
总尝试数：8110
来源：《信息学奥赛一本通》 , USACO , kuangbin专题 , POJ3278
算法标签
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int dist[N];
queue<int> q;
int bfs()
{
q.push(n);
memset(dist,-1,sizeof(dist));
dist[n]=0;
while(q.size())
{
auto t= q.front();
q.pop();
if (t == k) return dist[k];
if(t+1<N&&dist[t+1]==-1)
{
q.push(t+1);
dist[t+1]=dist[t]+1;
}
if(t-1>=0&&dist[t-1]==-1)
{
q.push(t-1);
dist[t-1]=dist[t]+1;
}
if(t*2<N&&dist[t*2]==-1)
{
q.push(t*2);
dist[t*2]=dist[t]+1;
}
}
}
int main()
{
cin>>n>>k;
cout<<bfs()<<endl;
return 0;
}
(8)最优乘车
H 城是一个旅游胜地，每年都有成千上万的人前来观光。
为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。
现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。
写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。
输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。
数据范围
1≤M≤100,
2≤N≤500
输入样例：
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2
代码
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=505;
int n,m,dist[N],stop[N];
bool g[N][N];
void bfs()
{
memset(dist,0,sizeof(dist));
queue<int> q;
q.push(1);
while(q.size())
{
int t =q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(g[t][i]&&!dist[i])
{
dist[i]=dist[t]+1;
q.push(i);
}
}
}
}
int main()
{
cin>>m>>n;
string line;
getline(cin,line);
while(m--)
{
getline(cin,line);
stringstream ssin(line);
int cnt=0,p;
while(ssin>>p)stop[cnt++]=p;
for(int i=0;i<cnt;i++)
{
for(int j=i+1;j<cnt;j++)
{
g[stop[i]][stop[j]]=1;
}
}
}
bfs();
if(!dist[n]) cout<<"NO"<<endl;
else cout<<dist[n]-1<<endl;
return 0;
}
总结:边权为1的图找最短路用BFS
牛逼