QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662148#8236. Snake Movekur222TL 0ms3668kbC++233.2kb2024-10-20 21:29:382024-10-20 21:29:39

Judging History

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

  • [2024-10-20 21:29:39]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3668kb
  • [2024-10-20 21:29:38]
  • 提交

answer

#pragma GCC optimize(2, "Ofast", "inline")
#include <bits/stdc++.h>
// using pair<int,int>= pair<int,int>;
// using tuple<int,int,int>= tuple<int,int,int>;
using ll = long long;
using ull = unsigned long long;
using namespace std;
const int inf = 1e9;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<pair<int, int>> snack(k);
    vector<int> mp(n * m, 0);
    for (int i = 0; i < k; i++)
    {
        cin >> snack[i].first >> snack[i].second;
        snack[i].first--;
        snack[i].second--;
        if (i)
             mp[snack[i].first * m + snack[i].second] = k - i;

    }

    vector<string> qizi(n);
    for (int i = 0; i < n; i++)
    {
        cin >> qizi[i];
    }

    int odir = 0;
    if(k>1)
    {for (int i = 0; i < 4; i++)
    {
        if (snack[1].first + dx[i] == snack[0].first && snack[1].second + dy[i] == snack[0].second)
        {
            odir = i;
        }
    }}

    vector<array<int, 4>> f(n * m, {inf, inf, inf, inf});
    // f[snack[0].first][snack[0].second] = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push({0, odir, snack[0].first * m + snack[0].second});
    while (!pq.empty())
    {
        auto [d, dir, pos] = pq.top();
        pq.pop();
        int x = pos / m;
        int y = pos % m;
        if (f[pos][dir] != inf)
        {
            continue;
        }
        // cerr << x + 1 << " " << y + 1 << " " << d << endl;
        f[pos][dir] = d;
        for (int i = 0; i < 4; i++)
        {
            if (dir == (i + 2) % 4)
                continue;
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#')
                continue;
            pq.push({max(mp[nx*m+ny], d + 1), i, nx * m + ny});
            // cout << nx << " " << ny << endl;
        }
    }

    int tim = k - 2;
    tim = max(0, tim);
    queue<tuple<int, int, int>> q;
    q.push({snack[0].first, snack[0].second, tim});
    vector<int> dis(n * m, inf);
    dis[snack[0].first * m + snack[0].second] = tim;
    while (!q.empty())
    {
        auto [x, y, d] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#')
                continue;
            if (dis[nx * m + ny] == inf)
            {
                dis[nx * m + ny] = min(d + 1, dis[nx * m + ny]);
                q.push({nx, ny, d + 1});
            }
        }
    }

    ull res = 0;
    for (int i = 0; i < n * m; i++)
    {
        int ans = dis[i];
        for (int j = 0; j < 4; j++)
        {
            ans = min(ans, f[i][j]);
        }
        if (ans == inf)
        {
            ans = 0;
        }
        // cerr << ans << " \n"[(i + 1) % m == 0];
        res += 1ll * ans * ans;
    }

    cout << res << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int tt = 1;
    // std::cin >> tt;
    while (tt--)
        solve();
}

詳細信息

Test #1:

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

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: 3668kb

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: 3572kb

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: