QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547527#8236. Snake MoveChuggWA 0ms3860kbC++202.0kb2024-09-04 22:27:232024-09-04 22:27:24

Judging History

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

  • [2024-09-04 22:27:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-09-04 22:27:23]
  • 提交

answer

#include <bits/stdc++.h>

constexpr int ds[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void solve() 
{
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::pair<int, int>> a(k);
    for (auto &[x, y] : a) {
        std::cin >> x >> y;
        x--, y--;
    }
    std::vector<std::string> s(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    } 
    int cnt = 1;
    std::vector ans(n, std::vector<int>(m));
    for (const auto &[x, y] : a) {
        ans[x][y] = -cnt;
        cnt++;
    }
    std::queue<std::pair<int, int>> q, tq;
    ans[a[0].first][a[0].second] = 1;
    q.emplace(a[0]);
    while (!q.empty()) {
        auto [x, y] = q.front();
        if (!tq.empty()) {
            auto [tx, ty] = tq.front();
            if (ans[tx][ty] <= ans[x][y]) {
                x = tx;
                y = ty;
                tq.pop();
            } else {
                q.pop();
            }
        } else {
            q.pop();
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + ds[i][0];
            int ny = y + ds[i][1];
            if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
            if (s[nx][ny] == '#') continue;
            if (ans[nx][ny] == 0) {
                ans[nx][ny] = ans[x][y] + 1;
                q.emplace(nx, ny);
            }
            if (ans[nx][ny] < 0) {
                ans[nx][ny] = std::max(k + ans[nx][ny] + 2, ans[x][y] + 1);
                tq.emplace(nx, ny);
            }
        }
    }
    uint64_t sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (ans[i][j] > 0) ans[i][j]--;
            else ans[i][j] = 0;
            sum = sum + (uint64_t)ans[i][j] * (uint64_t)ans[i][j];
            // std::cout << ans[i][j] << " \n"[j == m - 1];
        }
    }
    std::cout << sum << '\n';
}

int main() 
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
    
    int t = 1;
    while(t--) {
        solve();
    }
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3580kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

10

result:

wrong answer 1st lines differ - expected: '14', found: '10'