QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#585151 | #8236. Snake Move | Fiatiustitia | WA | 457ms | 119200kb | C++20 | 2.4kb | 2024-09-23 19:24:05 | 2024-09-23 19:24:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
const int INF = 1e9;
vector dis(n, vector<int>(m, INF));
vector to_back(n, vector<int>(m, 0)), vis(n, vector<int>(m, 0));
vector<string> g(n);
auto check = [&](int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#';
};
using P = pair<int, int>;
vector<P> snake(k);
for (int i = 0; i < k; i++)
{
auto &[x, y] = snake[i];
cin >> x >> y;
x--, y--;
to_back[x][y] = k - 1 - i;
}
using T = array<int, 3>;
priority_queue<T> p;
queue<T> q;
for (auto &s : g)
cin >> s;
q.push(T({0,snake[0].first, snake[0].second}));
dis[snake[0].first][snake[0].second] = 0;
while (!q.empty())
{
auto [ta, xa, ya] = q.front();
int x = xa,y = ya,t = ta;
if (!p.empty())
{
auto [tb,xb,yb] = p.top();
tb = -tb;
if (tb < ta)
{
x = xb,y = yb,t = tb;
p.pop();
}
else
{
q.pop();
}
}
else
q.pop();
if (vis[x][y])
continue;
vis[x][y] = 1;
for (int i = 0; i < 4; i++)
{
auto [nx, ny] = P(x + dir[i][0], y + dir[i][1]);
if (!check(nx, ny) || vis[nx][ny])
continue;
if (to_back[nx][ny])
{
dis[nx][ny] = min(dis[nx][ny], t + 1 + max(0,to_back[nx][ny] - dis[x][y]));
p.push(T({-dis[nx][ny],nx,ny}));
}
else
{
dis[nx][ny] = min(dis[nx][ny], t + 1);
q.push(T({dis[nx][ny], nx, ny}));
}
}
}
uint64_t res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (dis[i][j] == INF)
continue;
res += 1ull * dis[i][j] * dis[i][j];
}
cout << res << '\n';
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
auto t = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
#ifdef LOCAL
cerr << clock() - t << '\n';
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 416ms
memory: 115448kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 457ms
memory: 115456kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 16ms
memory: 118864kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 24ms
memory: 114688kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 410ms
memory: 115624kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: 0
Accepted
time: 438ms
memory: 119200kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749285
result:
ok single line: '22509095749285'
Test #10:
score: 0
Accepted
time: 16ms
memory: 114756kb
input:
3000 2900 10 326 1781 325 1781 325 1782 325 1783 325 1784 324 1784 324 1783 323 1783 323 1782 324 1782 ##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...
output:
40571
result:
ok single line: '40571'
Test #11:
score: -100
Wrong Answer
time: 19ms
memory: 114952kb
input:
2900 3000 10 2447 135 2447 136 2447 137 2447 138 2447 139 2447 140 2448 140 2448 139 2449 139 2449 138 .#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...
output:
251
result:
wrong answer 1st lines differ - expected: '2705', found: '251'