QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#96315 | #5153. Delft Distance | Ahmed_Abdelmegeed# | WA | 2ms | 7724kb | C++20 | 5.0kb | 2023-04-13 19:23:11 | 2023-04-13 19:23:16 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 700 + 10, INF = 1e18;
const ld pi = acos(-1);
const int mod = 1e9 + 7, LOG = 20;
const ld eps = 1e-4;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = { -1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, x, y;
ld sidecircle = 0.5 * pi * 5;
ld dis[N][N][10], vis[N][N][10];
char grid[N][N];
void zbtsquare(int x, int y) {
ld cur;
for (int i = 0; i < 8; i++) {
cur = 0;
for (int j = i; j < i + 8; j++) {
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += 5;
}
cur = 0;
for (int j = i; j > i - 8; j--) {
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += 5;
}
}
}
void zbtcircle(int x, int y) {
ld cur;
for (int i = 1; i < 8; i += 2) {
cur = 0;
for (int j = i; j < i + 8; j += 2) {
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += sidecircle;
}
cur = 0;
for (int j = i; j > i - 8; j -= 2) {
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += sidecircle;
}
}
}
bool valid(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void trantition(int x, int y) {
dis[x - 1][y][6] = min(dis[x - 1][y][6], dis[x][y][2]);
dis[x][y + 1][0] = min(dis[x][y + 1][0], dis[x][y][2]);
dis[x][y + 1][7] = min(dis[x][y + 1][7], dis[x][y][3]);
dis[x][y + 1][6] = min(dis[x][y + 1][6], dis[x][y][4]);
dis[x + 1][y + 1][0] = min(dis[x + 1][y + 1][0], dis[x][y][4]);
dis[x + 1][y][2] = min(dis[x + 1][y][2], dis[x][y][4]);
dis[x + 1][y][1] = min(dis[x + 1][y][1], dis[x][y][5]);
dis[x + 1][y][0] = min(dis[x + 1][y][0], dis[x][y][6]);
dis[x - 1][y + 1][2] = min(dis[x - 1][y + 1][2], dis[x][y][6]);
dis[x][y - 1][2] = min(dis[x][y - 1][2], dis[x][y][0]);
dis[x][y - 1][3] = min(dis[x][y - 1][3], dis[x][y][7]);
dis[x][y - 1][4] = min(dis[x][y - 1][4], dis[x][y][6]);
dis[x - 1][y - 1][4] = min(dis[x - 1][y - 1][4], dis[x][y][0]);
dis[x - 1][y][6] = min(dis[x - 1][y][6], dis[x][y][0]);
dis[x - 1][y][5] = min(dis[x - 1][y][5], dis[x][y][1]);
dis[x - 1][y][4] = min(dis[x - 1][y][4], dis[x][y][2]);
}
void solve() {
priority_queue<pair<ld, pair<pair<int, int>, int>>> pq;
dis[1][1][0] = 0;
zbtsquare(1, 1);
if (grid[1][1] == 'O') {
zbtcircle(1, 1);
}
for (int i = 0; i < 8; i++) {
//cout << i << " " << dis[1][1][i] << el;
pq.push({ -dis[1][1][i], {{1, 1}, i}});
vis[1][1][i] = dis[1][1][i];
}
ld cost;
//cout << "HERE" << el;
int state, nx, ny;
while (pq.size()) {
x = pq.top().second.first.first;
y = pq.top().second.first.second;
cost = -pq.top().first;
state = pq.top().second.second;
pq.pop();
if (dis[x][y][state] != cost) {
continue;
}
trantition(x, y);
//cout << x << " " << y << el;
for (int i = 0; i < 8; i++) {
nx = x + dx[i], ny = y + dy[i];
for (int j = 0; j < 8; j++) {
if (vis[nx][ny][j] > dis[nx][ny][j] && valid(nx, ny)) {
vis[nx][ny][j] = dis[nx][ny][j];
//cout << x << " " << y << " " << nx << " " << ny << el;
//cout << vis[nx][ny][j] << " " << dis[nx][ny][j] << el;
zbtsquare(nx, ny);
//cout << nx << " " << ny << el;
if (grid[nx][ny] == 'O') {
zbtcircle(nx, ny);
}
pq.push({ -dis[nx][ny][j], {{nx, ny}, j}});
}
}
}
//return;
}
}
void dowork() {
cin >> n >> m;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= 8; k++) {
dis[i][j][k] = vis[i][j][k] = 2e18;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
}
}
solve();
cout << fixed << setprecision(8) << dis[n][m][4] << el;
}
signed main() {
fast
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
dowork();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7724kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.41592654
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5788kb
input:
1 4 XOOX
output:
45.70796327
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5648kb
input:
1 1 X
output:
20.00000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 5784kb
input:
1 1 O
output:
20.00000000
result:
wrong answer 1st numbers differ - expected: '17.8539816', found: '20.0000000', error = '0.1201983'