题解：AT_abc170_f [ABC170F] Pond Skater
CommandSR
2024-11-16 16:29:09
BFS + 优化
数据存储
$ ，普通数组空间存不下。
考虑用 vector。
```cpp
vector <char> a[1000010];
vector <int> dis[1000010];
```
地图数组和记录数组都需要 vector ，输入时都要 push_back。
---
### 每次可以走 1~k 步
在 BFS 模板枚举方向的同时，加上一层循环。
注意一旦**碰到障碍（即不能跳过石头），移出边界，或被标记过**，若当前在走第 $j$ 步，则后面的 $[j+1, k]$ 均不可走。
```cpp
for (int i = 0; i < 4; i++)
{
for (int j = 1; j <= k; j++)
{
v.x = u.x + dx[i] * j;
v.y = u.y + dy[i] * j;
if (v.x < 0 || v.x >= n || v.y < 0 || v.y >= m) break ;
if (dis[v.x][v.y] && dis[v.x][v.y] <= dis[u.x][u.y]) break ;
if (dis[v.x][v.y]) continue ;
if (a[v.x][v.y] == '@') break ;
q.push(v);
dis[v.x][v.y] = dis[u.x][u.y] + 1;
}
}
```
---
### 剪枝
用上述方法通过将超时。
**注意到本来只需走 $k$ 步，但是如果路途中间遇到了一样近或更近的点就可以停止了，显然，后面那些没走的位置可以通过这个点走过去而不会更劣。**
```cpp
if (dis[v.x][v.y] && dis[v.x][v.y] <= dis[u.x][u.y]) break ;
```
---
#### 其余细节见注释
### AC CODE
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, k, sx, sy, tx, ty;
vector <char> a[1000010];
vector <int> dis[1000010];
struct node
{
int x, y;
};
queue <node> q;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
void bfs()
{
q.push((node){sx, sy});
dis[sx][sy] = 1;
while (!q.empty())
{
node u = q.front(), v;
q.pop();
for (int i = 0; i < 4; i++)
{
for (int j = 1; j <= k; j++) // 可以走1~k步
{
v.x = u.x + dx[i] * j;
v.y = u.y + dy[i] * j;
if (v.x < 0 || v.x >= n || v.y < 0 || v.y >= m) break ;
if (dis[v.x][v.y] && dis[v.x][v.y] <= dis[u.x][u.y]) break ; // 剪枝
if (dis[v.x][v.y]) continue ;
if (a[v.x][v.y] == '@') break ;
// 注意上文提到的直接 break 的情况
q.push(v);
dis[v.x][v.y] = dis[u.x][u.y] + 1; // 步数 + 1
}
}
}
if (dis[tx][ty]) cout << dis[tx][ty] - 1; // 最终答案
else cout << -1;
}
int main()
{
// freopen("b.in", "r", stdin);
// freopen("b.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
cin >> sx >> sy >> tx >> ty;
// 由于vector存储，下标从0开始，故读入的起点和终点坐标数据要-1
sx--, sy--, tx--, ty--;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
char ch;
cin >> ch;
a[i].push_back(ch);
dis[i].push_back(0);
// vector 存储，注意dis数组也要push_back()，否则后面无法修改访问dis数组元素
}
}
bfs();
return 0;
}
```