QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#845143 | #8236. Snake Move | Red0 | TL | 0ms | 3792kb | C++20 | 2.8kb | 2025-01-06 15:07:06 | 2025-01-06 15:07:06 |
Judging History
answer
#pragma GCC optimize("03")
#include <bits/stdc++.h>
using namespace std;
// Type aliases for convenience
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vc = vector<char>;
using vvc = vector<vc>;
// Constants
const int INF = 1e9;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
// Represents if a square is part of the snake and its distance+1 from the head
map<pii, int> org_snake;
int hx = 0, hy = 0, tx = 0, ty = 0;
// Input for snake positions
for (int i = 1; i <= k; ++i) {
int x, y;
cin >> x >> y;
if (i == 1) hx = x, hy = y; // Head of the snake
else if (i == k) tx = x, ty = y; // Tail of the snake
org_snake[{x, y}] = i; // Distance+1 of the body part
}
// Input grid
vvc grid(n + 1, vc(m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> grid[i][j];
// Initialize distance grid and priority queue
vvi dist(n + 1, vi(m + 1, INF));
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq;
// Start BFS from the head of the snake
pq.push({0, 0, hx, hy});
while (!pq.empty()) {
auto [csteps, hasremoved, cx, cy] = pq.top();
pq.pop();
if (dist[cx][cy] != INF) continue; // Already visited
dist[cx][cy] = csteps;
// Explore neighbors
for (int i = 0; i < 4; ++i) {
int nx = cx + dx[i], ny = cy + dy[i];
// Check bounds and obstacles
if (nx < 1 || nx > n || ny < 1 || ny > m || grid[nx][ny] == '#' || dist[nx][ny] != INF)
continue;
if (org_snake[{nx, ny}] != 0) { // Snake body part
int steps_needed = org_snake[{tx, ty}] - org_snake[{nx, ny}] - csteps;
if (steps_needed > 0) {
if (hasremoved) {
pq.push({csteps + 1, 1, nx, ny});
} else {
pq.push({csteps + 1 + steps_needed, 1, nx, ny});
}
} else {
pq.push({csteps + 1, hasremoved, nx, ny});
}
} else { // Normal move
pq.push({csteps + 1, hasremoved, nx, ny});
}
}
}
// Calculate the answer
uint64_t ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (dist[i][j] != INF) {
ans += static_cast<uint64_t>(dist[i][j]) * dist[i][j];
}
}
}
// Output the result
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3788kb
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: 3792kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Time Limit Exceeded
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................