方格迷宫
给定一个 $n$ 行 $m$ 列的方格矩阵。
行从上到下依次编号为 $1 \sim n$,列从左到右依次编号为 $1 \sim m$。
第 $i$ 行第 $j$ 列的方格表示为 $(i,j)$。
矩阵中的方格要么是空地(用 . 表示),要么是陷阱(用 # 表示)。
初始时,你位于方格 $(x_1,y_1)$,你需要前往方格 $(x_2,y_2)$。
每次移动,你可以任选上、下、左、右四个方向之一,并沿该方向移动 $1 \sim k$ 步。
从一个方格移动至相邻方格视为一步。
但是,你要保证在你的移动过程中不能走出矩阵,也不能进入陷阱方格。
请你计算从方格 $(x_1,y_1)$ 移动至方格 $(x_2,y_2)$,所需要的最少移动次数。
保证方格 $(x_1,y_1)$ 和方格 $(x_2,y_2)$ 都是空地。
方格 $(x_1,y_1)$ 和方格 $(x_2,y_2)$ 可能是同一个方格。
注意:注意区分本题中移动次数与移动步数的区别。
输入格式
第一行包含三个整数 $n,m,k$。
接下来 $n$ 行,每行包含 $m$ 个字符,其中第 $i$ 行第 $j$ 个字符,要么是 .,表示方格 $(i,j)$ 是空地;要么是 #,表示方格 $(i,j)$ 是陷阱。
最后一行包含四个整数 $x_1,y_1,x_2,y_2$。
输出格式
一个整数,表示所需要的最少移动次数。
如果无法从方格 $(x_1,y_1)$ 移动至方格 $(x_2,y_2)$,则输出 $-1$。
数据范围
前 $6$ 个测试点满足 $1 \leq n,m \leq 10$。
所有测试点满足 $1 \leq n,m,k \leq 1000$,$1 \leq x_1,x_2 \leq n$,$1 \leq y_1,y_2 \leq m$。
输入样例1:
3 4 4 .... ###. .... 1 1 3 1
输出样例1:
3
输入样例2:
3 4 1 .... ###. .... 1 1 3 1
输出样例2:
8
输入样例3:
2 2 1 .# #. 1 1 2 2
输出样例3:
-1
解题思路
很容易想到$\text{bfs}$,然后在枚举$4$个方向时再枚举这个方向要走的长度,因此这样做的时间复杂度为$O(nmk)$。这题有个比较巧妙的剪枝,假设当前位置是$(x,y)$,到该位置的距离是$d_{x,y}$,在同一个方向上枚举要走的长度,当枚举到$(x + dx, y + dy)$且$d_{x + dx, y + dy} < d_{x,y} + 1$,那么之后的格子可以用$(x + dx, y + dy)$这个位置来更新,因为$d_{x + dx, y + dy} < d_{x,y} + 1$,因此有$d_{x + dx, y + dy} + 1 \leq d_{x,y} + 1$,因此用$(x + dx, y + dy)$来更新后面的格子取值不会变大。因此在枚举的过程中发现$d_{x + dx, y + dy} < d_{x,y} + 1$直接$\text{break}$就好了。
加上这个剪枝后时间复杂度就变成了$O(nm)$。可以证明在同一个方向上每个格子最多会被枚举到$2$次,因此$4$个方向一共最多被枚举$8 \cdot nm$。
假设距离为$d$的格子已经沿着一个方向把一些格子更新成了$d+1$,此时再从队列中弹出一个格子,根据$\text{bfs}$的性质这个格子的距离一定$\geq d$,因此当这个格子枚举到距离为$d$的格子或者已经被更新为$d+1$的格子时就会$\text{break}$掉。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef pair<int, int> PII; 5 6 const int N = 1010; 7 8 char g[N][N]; 9 int dist[N][N]; 10 PII q[N * N]; 11 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 12 13 int main() { 14 int n, m, k, x1, y1, x2, y2; 15 scanf("%d %d %d", &n, &m, &k); 16 for (int i = 0; i < n; i++) { 17 scanf("%s", g + i); 18 } 19 scanf("%d %d %d %d", &x1, &y1, &x2, &y2); 20 x1--, y1--, x2--, y2--; 21 memset(dist, 0x3f, sizeof(dist)); 22 dist[x1][y1] = 0; 23 int hh = 0, tt = -1; 24 q[++tt] = {x1, y1}; 25 while (hh <= tt) { 26 PII t = q[hh++]; 27 for (int i = 0; i < 4; i++) { 28 for (int j = 1; j <= k; j++) { 29 int x = t.first + dx[i] * j, y = t.second + dy[i] * j; 30 if (x < 0 || x >= n || y < 0 || y >= m) break; 31 if (g[x][y] == '#') break; 32 if (dist[x][y] < dist[t.first][t.second] + 1) break; 33 if (dist[x][y] > dist[t.first][t.second] + 1) { 34 dist[x][y] = dist[t.first][t.second] + 1; 35 q[++tt] = {x, y}; 36 } 37 } 38 } 39 } 40 printf("%d", dist[x2][y2] == 0x3f3f3f3f ? -1 : dist[x2][y2]); 41 42 return 0; 43 }
参考资料
AcWing 4943. 方格迷宫(第二届ACC(AcWing Cup)全国联赛):https://www.acwing.com/video/4683/