QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201377#5153. Delft DistanceRd_rainydays#RE 1ms6084kbC++201.1kb2023-10-05 14:01:402023-10-05 14:01:40

Judging History

你现在查看的是最新测评结果

  • [2023-10-05 14:01:40]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:6084kb
  • [2023-10-05 14:01:40]
  • 提交

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...

output:


result: