QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#640904#8236. Snake MoveQSteve_PaulWA 0ms3472kbC++233.6kb2024-10-14 16:49:402024-10-14 16:49:45

Judging History

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

  • [2024-10-14 16:49:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3472kb
  • [2024-10-14 16:49:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;

constexpr u64 INF = -1;

void solve()
{
    const int dx[] = {-1, 0, 1, 0};
    const int dy[] = {0, 1, 0, -1};
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<u64>> f(n + 1, vector<u64>(m + 1, INF));
    vector<pair<int, int>> snk(k + 1);
    for (int i = 1; i <= k; i++)
        cin >> snk[i].first >> snk[i].second;
    vector<vector<int>> g(n + 2, vector<int>(m + 2));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char ch;
            cin >> ch;
            if (ch == '#')
                g[i][j] = 1;
            else
                g[i][j] = 0;
            ;
        }
    }
    for (int i = 0; i <= n + 1; i++)
    {
        for (int j = 0; j <= m + 1; j++)
        {
            if (i < 1 || i > n || j < 1 || j > m)
                g[i][j] = 1;
        }
    }

    vector<vector<u64>> lim(n + 1, vector<u64>(m + 1, INF));
    for (int i = 1; i <= k; i++)
    {
        auto [x, y] = snk[i];
        lim[x][y] = k + 1 - i;
    }

    struct node
    {
        int x, y;
        node(const int &x, const int &y) : x(x), y(y)
        {
        }
        node(const pair<int, int> &p) : x(p.first), y(p.second)
        {
        }
    };

    if (k == 1)
    {
        queue<pair<node, u64>> q;
        q.push({snk[1], 0ULL});
        while (!q.empty())
        {
            auto [p, t] = q.front();
            q.pop();
            if (t < f[p.x][p.y])
                f[p.x][p.y] = t;
            else
                continue;
            for (int i = 0; i < 4; i++)
            {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (g[nx][ny])
                    continue;
                q.push({{nx, ny}, t + 1});
            }
        }

        u64 ans = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (f[i][j] == INF)
                    continue;
                ans += f[i][j] * f[i][j];
            }
        }
        cout << ans << "\n";
        return;
    }
    struct state
    {
        node last;
        node now;
        u64 time;
        int len;
    };
    queue<state> q;
    q.push({snk[2], snk[1], 0, k});
    while (!q.empty())
    {
        state stt = q.front();
        u64 t = stt.time;
        node p = stt.now;
        node lp = stt.last;
        int len = stt.len;
        q.pop();
        if (t < f[p.x][p.y])
            f[p.x][p.y] = t;
        else
            continue;
        for (int i = 0; i < 4; i++)
        {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (g[nx][ny])
                continue;
            if (t + 1ULL < lim[nx][ny])
                continue;
            q.push({p, {nx, ny}, t + 1ULL, len});
        }
        q.push({p, lp, t + (u64)len - 1ULL, 2});
    }

    u64 ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (f[i][j] == INF)
                continue;
            ans += f[i][j] * f[i][j];
        }
    }
    cout << ans << "\n";
}

int main()
{
#ifdef lijn
    freopen("/home/lijn/acm_practice/.build/input.in", "r", stdin);
    freopen("/home/lijn/acm_practice/.build/output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3472kb

input:

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

output:

126

result:

wrong answer 1st lines differ - expected: '293', found: '126'