餐饮品牌设计网站,石家庄网站建设策划方案,南宁百度推广排名优化,一级建造师培训机构排名前十算法提高课笔记 目录 迷宫问题题意思路代码 武士风度的牛题意思路代码 抓住那头牛题意思路代码 BFS可以解决边权为1的最短路问题#xff0c;下面是三道相关例题 迷宫问题
原题链接
给定一个 nn 的二维数组#xff0c;如下所示#xff1a;
int maze[5][5] {0, 1, 0, 0, …算法提高课笔记 目录 迷宫问题题意思路代码 武士风度的牛题意思路代码 抓住那头牛题意思路代码 BFS可以解决边权为1的最短路问题下面是三道相关例题 迷宫问题
原题链接
给定一个 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题意
一个矩阵0代表有路1代表没有路问从左上角走到右下角的最短路径
思路
因为边权均为1所以利用BFS可以求出从起点到终点的最短路同时利用一个小技巧从终点往起点走即可在后续输出路径时正向输出
代码
#include bits/stdc.husing namespace std;const int N 1010, M N * N;typedef pairint, int PII;
#define ft first
#define sd secondint n;
int g[N][N];
queuePII q;
PII pre[N][N];void bfs(int x, int y)
{int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; // 代表上下左右四个移动方向q.push({x, y});memset(pre, -1, sizeof pre);while (q.size()){PII t q.front();q.pop();for (int i 0; i 4; i ){int a t.ft dx[i], b t.sd dy[i];if (a 0 || a n || b 0 || b n) continue; // 位置不合法if (g[a][b]) continue; // 没路if (pre[a][b].ft ! -1) continue; // 走过了q.push({a, b});pre[a][b] t;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n;for (int i 0; i n; i )for (int j 0; j n; j )cin g[i][j];bfs(n - 1, n - 1);PII end(0, 0);while (1){cout end.ft end.sd \n;if (end.ft n - 1 end.sd n - 1) break;end pre[end.ft][end.sd];}
}武士风度的牛
原题链接
农民 John 有很多牛他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力在农场里像 Knight 一样地跳就是我们熟悉的象棋中马的走法。
虽然这头神奇的牛不能跳到树上和石头上但是它可以在牧场上随意跳我们把牧场用一个 xy 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草给你一张地图上面标注了 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 | . . * . . * . . . F5 | * . B . . . . . . .4 | . . . * C . . * E .3 | .A . . . . D . . .2 | . . . * . . . . . *1 | . . * . . . . * . .0 ----------------------10 1 2 3 4 5 6 7 8 9 0注意 数据保证一定有解。
输入格式
第 1 行 两个数表示农场的列数 C 和行数 R。
第 2…R1 行: 每行一个由 C 个字符组成的字符串共同描绘出牧场地图。
输出格式
一个整数表示跳跃的最小次数。
数据范围
1 ≤ R , C ≤ 150
输入样例
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..输出样例
5题意
图中*代表没有路.代表有路求以日字型从K走到H的最短路
思路
dx dy改成向八个不同方向移其余思路一样第一次遍历到H时输出即可
代码
#include bits/stdc.husing namespace std;const int N 155, M N * N;typedef pairint, int PII;
#define ft first
#define sd secondint n, m;
char g[N][N]; // 存图
queuePII q;
int dist[N][N]; // 记录距离判重int bfs()
{int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2};int dy[8] {1, 2, 2, 1, -1, -2, -2, -1};int x, y;for (int i 0; i n; i )for (int j 0; j m; j )if (g[i][j] K)x i, y j;q.push({x, y});memset(dist, -1, sizeof dist);dist[x][y] 0;while (q.size()){auto t q.front();q.pop();for (int i 0; i 8; i ){int a t.ft dx[i], b t.sd dy[i];if (a 0 || a n || b 0 || b m) continue; // 位置不合法if (g[a][b] *) continue; // 没路if (dist[a][b] ! -1) continue; // 已遍历if (g[a][b] H) return dist[t.ft][t.sd] 1; // 走到终点dist[a][b] dist[t.ft][t.sd] 1;q.push({a, b});}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin m n;for (int i 0; i n; i ) cin g[i];cout bfs() \n;
}抓住那头牛
原题链接
农夫知道一头牛的位置想要抓住它。
农夫和牛都位于数轴上农夫起始位于点 N牛位于点 K。
农夫有两种移动方式
从 X 移动到 X−1 或 X1每次移动花费一分钟从 X 移动到 2∗X每次移动花费一分钟
假设牛没有意识到农夫的行动站在原地不动。
农夫最少要花多少时间才能抓住牛
输入格式
共一行包含两个整数N和K。
输出格式
输出一个整数表示抓到牛所花费的最少时间。
数据范围
0 ≤ N , K ≤ 105
输入样例
5 17输出样例
4题意
要求从N到K每次只能进行一个操作向右一步 / 向左一步 / 坐标变为现在的两倍求最短路
思路
这一题刚开始看第一反应是dp但后来发现BFS最短路来做也很简单
每次更新所有该轮操作可以到达的位置
无需更新负值因为只能通过-1到达负值而从负值到正值只能通过1二者相互抵消不可能是最短路
代码
#include bits/stdc.husing namespace std;const int N 100010;int n, k;
queueint q;
int dist[N];int bfs()
{memset(dist, -1, sizeof dist);dist[n] 0;q.push(n);while (q.size()){auto t q.front();q.pop();if (t k) return dist[k]; // 已到终点// 更新三个距离if (t 1 N dist[t 1] -1){dist[t 1] dist[t] 1;q.push(t 1);}if (t - 1 N dist[t - 1] -1){dist[t - 1] dist[t] 1;q.push(t - 1);}if (t * 2 N dist[t * 2] -1){dist[t * 2] dist[t] 1;q.push(t * 2);}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n k;cout bfs() \n;
}
