QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#842443#8236. Snake MoveEuclid73ML 0ms0kbC++142.9kb2025-01-04 13:00:262025-01-04 13:00:26

Judging History

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

  • [2025-01-04 13:00:26]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2025-01-04 13:00:26]
  • 提交

answer

//https://qoj.ac/problem/8236
#include <bits/stdc++.h>
using namespace std;

//need to use unsigned long long as it automatically makes them mod 2^64
#define ll long long
#define ull unsigned long long

//you just dijkstra+buckets the shortest path
//if the next node is from the original body and you have not already deleted it, you must wait until it is gone and then go into it

//buckets idea:
//make a bucket for each possible distance value and put nodes into the buckets.
//we can just go from bucket to next that way and it cuts out the logn factor from dijkstra.

const ll MAXN=3001;

ll n, m, k, ans, body[MAXN][MAXN], sx, sy, dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1}, rbound=1;
ull dist[MAXN][MAXN];
char grid[MAXN][MAXN];
queue<pair<ll, ll>> buckets[MAXN*MAXN];
bool vis[MAXN][MAXN];

void bfs()
{
    buckets[0].push({sx, sy});
    for (ull d=0; d<n*n; d++)
    {
        while (buckets[d].size()>0)
        {
            ll x=buckets[d].front().first, y=buckets[d].front().second;
            buckets[d].pop();
            if (vis[x][y])
            {
                continue;
            }
            //cout << x << " " << y << "\n";
            vis[x][y]=1;
            ll t=dist[x][y]+1;
            for (int i=0; i<4; i++)
            {
                ll r=x+dx[i], c=y+dy[i];
                if (r>=1 && r<=n && c>=1 && c<=m && grid[r][c]=='.' && !vis[r][c])
                {
                    if (body[r][c]>0 && body[r][c]>t)
                    {
                        if (dist[r][c]!=body[r][c])
                        {
                            dist[r][c]=body[r][c];
                            rbound=max(rbound, body[r][c]);
                            buckets[body[r][c]].push({r, c});
                        }
                    }
                    else
                    {
                        if (t<dist[r][c])
                        {
                            rbound=max(rbound, t);
                            dist[r][c]=t;
                            buckets[t].push({r, c});
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i=1; i<=k; i++)
    {
        ll x, y;
        cin >> x >> y;
        if (i==1)
        {
            sx=x;
            sy=y;
        }
        body[x][y]=k+1-i;
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            dist[i][j]=ULLONG_MAX;
            cin >> grid[i][j];
        }
    }
    dist[sx][sy]=0;
    bfs();
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (dist[i][j]!=ULLONG_MAX)
            {
                ans+=dist[i][j]*dist[i][j];
            }
            //cout << dist[i][j] << " ";
        }
        //cout << "\n";
    }
    cout << ans << "\n";
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

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

output:

293

result: