QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#842423 | #8236. Snake Move | Euclid73 | ML | 0ms | 0kb | C++14 | 2.8kb | 2025-01-04 12:47:46 | 2025-01-04 12:47:47 |
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;
const ull MAXDIST=1e7;
ll n, m, k, ans, body[MAXN][MAXN], sx, sy, dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};
ull dist[MAXN][MAXN];
char grid[MAXN][MAXN];
queue<pair<ll, ll>> buckets[MAXDIST];
bool vis[MAXN][MAXN];
void bfs()
{
buckets[0].push({sx, sy});
for (ull d=0; d<MAXDIST; 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];
buckets[body[r][c]].push({r, c});
}
}
else
{
if (t<dist[r][c])
{
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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293