[2020CCPC威海B] Labyrinth

Description

给定一张 (n imes m) 的棋盘，上面有 (k) 个障碍物，有 (q) 次询问，每次给定两个点 ((x_1,y_1), (x_2,y_2))，问这两点之间的最短路径长度。(ncdot m le 2 imes 10^5, k le 42, q le 10^5)

Solution

对于 ((x_1,y_1), (x_2,y_2)) 两点构成的最短路径，如果大于忽略障碍物时的曼哈顿距离，则一定有一条贴着障碍物的路径与它等长。

所谓贴着障碍物，就是路径上至少存在一个点，是障碍物的邻居。

因此，如果矩形 ((x_1,y_1) - (x_2,y_2)) 中没有障碍物，我们就直接用曼哈顿距离；否则，找到一个障碍物的邻居点 ((x_t,y_t))，使得路径 ((x_1,y_1) o (x_t,y_t) o (x_2,y_2)) 最短。

判断矩形中是否有障碍物显然可以暴力实现。

求最短距离，只需要预处理每一个障碍物邻居点到棋盘上所有点的最短距离即可。

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

const int N = 400005;
const int inf = 0x3f3f3f3f;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

set<pair<int, int>> s;
int *dis[50][4][N];

vector<pair<int, int>> holes;

int n, m, k, q;

struct Item
{
    int x, y, d;
};

int check(int x1, int y1, int x2, int y2)
{
    if (x1 > x2)
        swap(x1, x2);
    if (y1 > y2)
        swap(y1, y2);
    for (auto hole : holes)
    {
        int nx = hole.first, ny = hole.second;
        if (x1 <= nx && nx <= x2 && y1 <= ny && ny <= y2)
            return true;
    }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= k; i++)
    {
        int t1, t2;
        cin >> t1 >> t2;
        holes.push_back({t1, t2});
        s.insert({t1, t2});
    }
    for (int holeId = 0; holeId < holes.size(); holeId++)
    {
        auto hole = holes[holeId];
        int x = hole.first, y = hole.second;
        for (int pos = 0; pos < 4; pos++)
        {
            int nx = x + dx[pos], ny = y + dy[pos];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
            {
                for (int i = 0; i <= n + 1; i++)
                {
                    dis[holeId][pos][i] = new int[m + 5];
                    for (int j = 0; j <= m + 1; j++)
                        dis[holeId][pos][i][j] = inf;
                }
                if (s.find({nx, ny}) == s.end())
                {
                    queue<Item> que;
                    que.push({nx, ny, 0});
                    dis[holeId][pos][nx][ny] = 0;
                    while (que.size())
                    {
                        int nx = que.front().x, ny = que.front().y, nd = que.front().d;
                        que.pop();
                        for (int p = 0; p < 4; p++)
                        {
                            int tx = nx + dx[p], ty = ny + dy[p], td = nd + 1;
                            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && s.find({tx, ty}) == s.end()) if (dis[holeId][pos][tx][ty] == inf)
                            {
                                dis[holeId][pos][tx][ty] = td;
                                que.push({tx, ty, td});
                            }
                        }
                    }
                }
            }
        }
    }
    for (int t = 1; t <= q; t++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (check(x1, y1, x2, y2))
        {
            int ans = inf;
            for (int i = 0; i < k; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int nx = holes[i].first + dx[j], ny = holes[i].second + dy[j];
                    if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
                    {
                        ans = min(ans, dis[i][j][x1][y1] + dis[i][j][x2][y2]);
                    }
                }
            }
            if (ans < inf)
                cout << ans << endl;
            else
                cout << -1 << endl;
        }
        else
            cout << abs(x1 - x2) + abs(y1 - y2) << endl;
    }
    return 0;
}