最短路
AcWing1076. 迷宫问题
给定一个 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)。
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } inline LL read() { LL f = 1; LL x = 0;char ch = getchar();while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x * f; } const int N = 1010; int g[N][N]; PII pre[N][N]; LL n; void bfs(int x,int y) { queue<PII>q; q.push({ x,y }); pre[x][y] = { 0,0 }; memset(pre, -1, sizeof pre); pre[x][y] = { 0,0 }; int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 }; while (q.size()) { auto t = q.front(); q.pop(); for (int i = 0; i < 4;++i) { int xx = t.first + dx[i]; int yy = t.second + dy[i]; if (xx < 0 || xx >= n || yy < 0 || yy >= n)continue; if (pre[xx][yy].first != -1 || g[xx][yy] == 1)continue; q.push({ xx,yy }); pre[xx][yy] = t; } } } int main() { n = read(); for (int i = 0;i < n;++i) for (int j = 0;j < n;++j) g[i][j] = read(); bfs(n - 1, n - 1); PII end = { 0,0 }; while (1) { printf("%d %d\n", end.first, end.second); if (end.first == n - 1 && end.second == n - 1)break; end = pre[end.first][end.second]; } return 0; }
AcWing188. 武士风度的牛
农民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(C<=150)和行数R(R<=150)。
第2…R+1行: 每行一个由C个字符组成的字符串，共同描绘出牧场地图。
输出格式
一个整数，表示跳跃的最小次数。
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } inline LL read() { LL f = 1; LL x = 0;char ch = getchar();while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x * f; } const int N = 1010; char g[N][N]; int dis[N][N]; int n, m; int posx = 0, posy = 0; int bfs(int posx,int posy) { queue<PII>q; q.push({ posx,posy }); memset(dis, -1, sizeof dis); dis[posx][posy] = 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 xx = t.first + dx[i]; int yy = t.second + dy[i]; if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue; if (g[xx][yy] == '*' || dis[xx][yy] != -1)continue; if (g[xx][yy] == 'H')return dis[t.first][t.second] + 1; q.push({ xx,yy }); dis[xx][yy] = dis[t.first][t.second] + 1; } } } int main() { m = read(); n = read(); for (int i = 0;i < n;++i) cin >> g[i]; for (int i = 0;i < n;++i) { for (int j = 0;j < m;++j) { if (g[i][j] == 'K')posx = i, posy = j; } } cout << bfs(posx, posy) << endl; return 0; }
AcWing1100. 抓住那头牛
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
输入格式
共一行，包含两个整数N和K。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
0 ≤ N , K ≤ 105
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } inline LL read() { LL f = 1; LL x = 0;char ch = getchar();while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x * f; } const int N = 100100; int n, k; int dis[N]; int solve() { queue<int>q; q.push(n); memset(dis, -1, sizeof dis); dis[n] = 0; while(q.size()) { int t = q.front(); q.pop(); if (t == k)return dis[k]; if (t - 1 >= 0 && dis[t - 1] == -1) { q.push(t - 1); dis[t - 1] = dis[t] + 1; } if (t + 1 < N && dis[t + 1] == -1) { q.push(t + 1); dis[t + 1] = dis[t] + 1; } if (t * 2 < N && dis[t * 2] == -1) { q.push(t * 2); dis[t * 2] = dis[t] + 1; } } return -1; } int main() { n = read(); k = read(); cout << solve() << endl; return 0; }
