AT_abc241_f 题解

· · 题解

Part 1 题面翻译

高桥来到了一个 H \times W 的溜冰场，场上有 N 个障碍物，第 i 个障碍物的位置是 (X_i,Y_i)，高桥想从 (s_x,s_y) 出发，走到 (g_x,g_y)。

高桥每一步可以从上、下、左、右四个方向中选择一个，一直移动，直到碰到障碍物为止，他会停在障碍物之前的格子上。由于溜冰场四周都是悬崖峭壁，因此他不能向一个没有障碍物的方向移动。

输出最少的移动步数，若不能到达目标点，输出 -1。（必须正好停在目标点上，经过目标点没停下不算到达）

Part 2 解法思路

这道题求最优解，一看就知道是 BFS。

然而溜冰场很大，若是一步步地挪去找障碍显然会 TLE 到到飞起。

于是我们可以用 set 记录下每一行和每一列 分别有哪些障碍，这样向四个方向移动是就可以直接二分出该方向最近的障碍即可，可以使用 lower_bound。这就是为什么题目里说“必须正好停在目标点上，经过目标点没停下不算到达”了。

记录每一行和每一列分别有哪些障碍和从起点到各个点的距离等数据时，若是直接用数组存，显然直接 MLE 炸掉。我们可以用 map 代替数组存数据。

这道题看似是 BFS 模板题，其实也教会我们要学习使用 STL 帮助算法的实现。

Part 3 代码实现

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll h, w, n, sx, sy, ex, ey;
map<ll, set<ll> > x, y;
map<pair<ll, ll>, ll> d;
queue<pair<ll, ll> > q;

int main() {

    cin >> h >> w >> n >> sx >> sy >> ex >> ey;
    for (ll i = 1; i <= n; i++) {
        ll u, v;
        cin >> u >> v;
        x[u].insert(v);
        y[v].insert(u);
    }

    q.push({sx, sy});
    d[{sx, sy}] = 0;

    while (!q.empty()) {
        ll u = q.front().first, v = q.front().second;
        q.pop();
        if (u == ex && v == ey) {
            cout << d[{u, v}];
            return 0;
        }
        auto it = x[u].lower_bound(v);
        if (it != x[u].begin()) {
            if (d.find({u, *prev(it) + 1}) == d.end()) {
                q.push({u, *prev(it) + 1});
                d[{u, *prev(it) + 1}] = d[{u, v}] + 1; 
            }
        }
        if (it != x[u].end()) {
            if (d.find({u, *it - 1}) == d.end()) {
                q.push({u, *it - 1});
                d[{u, *it - 1}] = d[{u, v}] + 1; 
            }
        }
        it = y[v].lower_bound(u);
        if (it != y[v].begin()) {
            if (d.find({*prev(it) + 1, v}) == d.end()) {
                q.push({*prev(it) + 1, v});
                d[{*prev(it) + 1, v}] = d[{u, v}] + 1; 
            }
        }
        if (it != y[v].end()) {
            if (d.find({*it - 1, v}) == d.end()) {
                q.push({*it - 1, v});
                d[{*it - 1, v}] = d[{u, v}] + 1; 
            }
        }
    }
    cout << -1;

    return 0;
}