QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201377 | #5153. Delft Distance | Rd_rainydays# | RE | 1ms | 6084kb | C++20 | 1.1kb | 2023-10-05 14:01:40 | 2023-10-05 14:01:40 |
Judging History
answer
#include <bits/stdc++.h>
const double pi = acos(-1);
const double EPS = 1e-9;
const int N = 1405;
using pid = std::pair<int, double>;
int n, m;
char map[N][N];
std::vector<pid> rg[N];
int id[N][N], tot;
double dp[N * N];
double solve(int x) {
if (x == 1) return 0;
if (dp[x] > EPS) return dp[x];
dp[x] = 1e18;
for (auto [y, w] : rg[x])
dp[x] = std::min(dp[x], solve(y) + w);
return dp[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", map[i] + 1);
for (int i = 0; i <= 2 * n; i++)
for (int j = 0; j <= 2 * m; j++) {
id[i][j] = ++tot;
if (i && j % 2 == 0) rg[id[i][j]].emplace_back(id[i - 1][j], 5);
if (j && i % 2 == 0) rg[id[i][j]].emplace_back(id[i][j - 1], 5);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] == 'X') continue;
rg[id[2 * i - 1][2 * j]].emplace_back(id[2 * i - 2][2 * j - 1], 2.5 * pi);
rg[id[2 * i][2 * j - 1]].emplace_back(id[2 * i - 1][2 * j - 2], 2.5 * pi);
}
}
printf("%.10f", solve(id[n * 2][m * 2]));
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5968kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.4159265359
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5944kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6012kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 6016kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5996kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.8318530718
result:
ok found '142.8318531', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
1 2 XX
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
10 1 X X X O O O X O O X
output:
105.7079632679
result:
ok found '105.7079633', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 6084kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.2477796077
result:
ok found '214.2477796', expected '214.2477796', error '0.0000000'
Test #11:
score: -100
Runtime Error
input:
40 9 OOOOXOXXX XOXXXOXXO OXOXXXXXO OXOXXXOXX XXXXOXOXX XXOOXOXXX XOOXOXXXX XOXXOOXOX OXXOOOOXX XXOOOXXOO OXOOXOXXX OOOOOXOOO OXXXXXXXO OOOOOOOXX OOOXXXOOX OXOXXOOOO OOOOXOXOO OXOXOOOXO OXXOOXXXO OXOOXOOXO XXXOXOXOO XXOOOXOOX OOXXOOXOO XOOXXXXOX OXXXXOOOO OXOOOOXOX XXOXXXOOO OOXOOOXXX OXOOOOXOO OXOOO...