zhangas

Pay more attention

0%

D - Delft Distance

Posted on

D - Delft Distance

难度：⭐⭐

类型： 图论

题意：

​ 你现在地图西北角，想去东南角的比赛地点。要到那里，必须穿过这座城市的历史中心。这座城市由$h*w$的建筑网格组成，不仅有方形的住宅建筑，还有一些圆形的中世纪塔楼。所有的方形建筑都以$10m$的边长轴线排列，所有的圆形塔的直径都是$10m$。在两座相邻的建筑之间有一条宽度可以忽略不计的小巷子。

​ 你需要找到一条从酒店到比赛地点的最短路径，输出从西北角到东南角的最短路径的长度，以米为单位。您的答案的绝对误差最多$1e^{-6}$

​ 数据范围：$h(1\le h\le 700)$，$w(1\le w\le700)$

模型

图1：样例1——红色的是最短路径

单源最短路径

image-20240807102258431
图2：建图所需的顶点

​ 并非地图上的所有点都需要建立，我们只需要建立每个方格对应上、下、左、右四个方向的结点，和结点之间的边，跑一次Dijkstra单源最短路即可。

解的表示

​ $double\space dist[N]$表示压缩后的结点，距离出发点的最短距离，跑完Dijkstra单源最短路后，右下角方格$(n, m)$对应下面和右边的点加上到终点的$5.0m$，即

$\pmb{min(dist[hashed(n, m, 2)],\space dist[hashed(n, m, 4)]) + 5.0}$就是我们的答案。

时间复杂度

​ 节点数$N=wh$，跑Dijkstra最短路需要$O(NlogN)$，复杂度为$O(whlog(wh))$

实现

id函数

​ 将$(x, y)$坐标压到一维，$D=(x - 1) * (2 * m + 1) + y$

hashed函数

​ 计算第$(i,j)$个建筑物，上下左右四个方向对应的坐标。$\pmb{f\in [1,2,3,4]}$分别对应上、下、左、右四个方向。

addall函数

对于当前的方格，无论是$’X’$还是$’O’$，都建立从四个顶点出发，到八个方向的有向边，长度均为$10m$。

direction

图3：四个顶点对应的八条有向边

addo函数

对于当前的所有$’O’$的方格，建立沿圆形$\frac{1}{4}$弧的边，长度均为$\frac{1}{4}2\pi*(10*\frac{1}{2})m$

image-20240807101428234

图4：'O'方格的两个圆弧的边

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define PI acos(-1)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define PII pair<int, int>
// #define int long long
using namespace std;
const int N = 2e6 + 5;
int n, m;
int id(int x, int y)
{
    return (x - 1) * (2 * m + 1) + y;
}
int hashed(int x, int y, int f)
{
    if (f == 1)
    {
        return id((x - 1) * 2 + 1, y * 2);
    }
    else if (f == 2)
    {
        return id(x * 2 + 1, y * 2);
    }
    else if (f == 3)
    {
        return id(x * 2, (y - 1) * 2 + 1);
    }
    return id(x * 2, y * 2 + 1);
}

char s[1505][1505];
vector<pair<double, int>> g[N];
void addall(int x, int y)
{
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 1)});
    g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 3)});

    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 3)});

    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 1)});
    g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 3)});

    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 1)});
    g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 3)});
}
void addo(int x, int y)
{
    double L = PI * 5.0 / 2.0;
    g[hashed(x, y, 1)].push_back({L, hashed(x, y, 4)});
    g[hashed(x, y, 3)].push_back({L, hashed(x, y, 2)});
}

int st[N];
double dist[N];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
double dijkstra()
{
    for (int i = 0; i < N; ++i)
        dist[i] = 2e9;
    dist[hashed(1, 1, 1)] = 5.0;
    dist[hashed(1, 1, 3)] = 5.0;
    q.push({5.0, hashed(1, 1, 1)});
    q.push({5.0, hashed(1, 1, 3)});
    while (q.size())
    {
        pair<double, int> t = q.top();
        q.pop();
        double distance = t.first;
        int u = t.second;
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = 0; i < g[u].size(); ++i)
        {
            int j = g[u][i].second;
            double d = g[u][i].first;
            if (dist[j] > dist[u] + d)
            {
                dist[j] = dist[u] + d;
                if (!st[j])
                {
                    q.push({dist[j], j});
                }
            }
        }
    }
    return min(dist[hashed(n, m, 2)], dist[hashed(n, m, 4)]) + 5.0;
}

void solves()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            addall(i, j);
            if (s[i][j] == 'O')
                addo(i, j);
        }
    printf("%.10lf", dijkstra());
}
signed main()
{
    IOS;
    int T = 1;
    // cin >> T;
    while (T--)
        solves();
}