QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#845143#8236. Snake MoveRed0TL 0ms3792kbC++202.8kb2025-01-06 15:07:062025-01-06 15:07:06

Judging History

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

  • [2025-01-06 15:07:06]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3792kb
  • [2025-01-06 15:07:06]
  • 提交

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

output:


result: