AcWing 188. 武士风度的牛
本题链接：AcWing 188. 武士风度的牛
本博客提供本题截图：
本题分析
dist数组：记录路径的长度，同时和pre数组一样，起到了判重的作用，因为我们初始化为-1，且我们会不断的更新dist数组，所以对于dist的值，如果为-1证明没有被更新，则可以更新，反之不可更新，相比较与上题，本题的起始位置和终点来自于输入的字符串，所以我们想要求起点的话，可以用两个for循环去求得，虽然是八扩散，但是为“日”字扩散，所以也用的向量的方式，最后注意本题的输入是先输入列再输入行。
AC代码
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 155, M = N * N; int n, m; int dist[N][N]; char g[N][N]; PII q[M]; int bfs() { memset(dist, -1, sizeof dist); int dx[8]= {-2, -1, 1, 2, 2, 1, -1, -2} int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; int x1, y1; for (int i = 0; i < n; i ++ ) for (int j = 0; j <m; j ++ ) if (g[i][j] == 'K') { x1 = i; y1 = j; break; } q[0] = {x1, y1}; dist[x1][y1] = 0; int hh = 0, tt = 0; while (hh <= tt) { auto t = q[hh ++]; for (int i = 0; i < 8; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (dist[a][b] != -1) continue; if (g[a][b] == '*') continue; dist[a][b] = dist[t.x][t.y] + 1; q[ ++ tt] = {a, b}; if (g[a][b] == 'H') return dist[a][b]; } } return -1; } int main() { scanf("%d%d", &m, &n); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); printf("%d", bfs()); return 0; }
AcWing 1100. 抓住那头牛
本题链接：AcWing 1100. 抓住那头牛
本博客提供本题截图：
本题分析
dist数组的作用和上题一致，bfs中三个if对应三个操作，如果操作合法则加入到队列中
AC代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 100010; int q[N]; int dist[N]; int n, k; int bfs() { memset(dist, -1, sizeof dist); q[0] = n; int hh = 0, tt = 0; dist[n] = 0; while (hh <= tt) { auto t = q[hh ++]; if (t + 1 < N && dist[t + 1] == -1) { q[ ++ tt] = t + 1; dist[t + 1] = dist[t] + 1; } if (t - 1 >= 0 && dist[t - 1] == -1) { q[ ++ tt] = t - 1; dist[t - 1] = dist[t] + 1; } if (t * 2 < N && dist[2 * t] == -1) { q[ ++ tt] = 2 * t; dist[2 * t] = dist[t] + 1; } if (t == k) return dist[t]; } return -1; } int main() { scanf("%d%d", &n, &k); printf("%d", bfs()); return 0; }
三、时间复杂度
关于最短路模型的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
