QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#140920 | #5153. Delft Distance | emailam# | WA | 1ms | 5896kb | C++20 | 1.6kb | 2023-08-16 23:25:58 | 2023-08-16 23:26:02 |
Judging History
answer
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cin.tie(nullptr), cout.tie(nullptr);
#include <bits/stdc++.h>
#define ll long long
#define double long double
using namespace std;
const int N = 705;
int n, m;
char arr[N][N];
double dp[N][N][4];
// 1 -> right to me
// 2 -> down
vector<vector<double>> fromTo[3] = {
{{1, 5, 0}, {2, 5, 0}},
{{0, 5, 1}, {2, 10 * acos(-1) / 4, 1}},
{{0, 5, 2}, {1, 10 * acos(-1) / 4, 2}},
};
double solve(int x, int y, int edge) {
if (x == n && y == m && !edge) {
return 0;
}
if (x > n || y > m)return 1e9;
double &ret = dp[x][y][edge];
if (ret != -1)return ret;
ret = 1e9;
if (arr[x][y] == 'X') {
ret = min(solve(x + 1, y, 0), solve(x, y + 1, 0)) + 10;
} else {
for (auto i: fromTo[edge]) {
ret = min(ret, solve(x + (i[2] == 2), y + (i[2] == 1), i[0]) + i[1]);
}
}
return ret;
}
void solve() {
cin >> n >> m;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k < 4; ++k) {
dp[i][j][k] = -1;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
}
}
for (int i = 0; i <= m; ++i) {
arr[n + 1][i] = 'X';
}
for (int i = 0; i <= n; ++i) {
arr[i][m + 1] = 'X';
}
cout << setprecision(8) << solve(0, 0, 0);
}
signed main() {
io
int t;
t = 1;
// cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3732kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.415927
result:
ok found '71.4159270', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 4 XOOX
output:
45.707963
result:
ok found '45.7079630', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
1 1 X
output:
20
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
1 1 O
output:
17.853982
result:
ok found '17.8539820', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
1 3 XOO
output:
35.707963
result:
ok found '35.7079630', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
1 5 OXOOO
output:
55.707963
result:
ok found '55.7079630', expected '55.7079633', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
147.12389
result:
wrong answer 1st numbers differ - expected: '142.8318531', found: '147.1238900', error = '0.0300496'