QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #791168 | #8236. Snake Move | Konjac16 | TL | 5ms | 42536kb | C++23 | 1.7kb | 2024-11-28 17:16:23 | 2024-11-28 17:16:24 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize (3,"Ofast","inline")
using namespace std;
typedef long long ll;
const int MAXN=3000+10;
const int mod=1e9+7;
int a[MAXN][MAXN];
int dis[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,k;cin>>n>>m>>k;
int sx,sy;
for(int i=1,x,y;i<=k;i++){cin>>x>>y,a[x][y]=i;
if(i==1)sx=x,sy=y;}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c;cin>>c;
if(c=='#')a[i][j]=-1;
}
priority_queue<tuple<int,int,int> >q;
q.emplace(0,sx,sy);
memset(dis,0x3f,sizeof(dis));
dis[sx][sy]=0;
while(!q.empty())
{
auto [d,x,y]=q.top();q.pop();
if(vis[x][y])continue;
cerr<<x<<' '<<y<<'\n';
vis[x][y]=1;
for(int t=0;t<4;t++)
{
int tx=x+dx[t],ty=y+dy[t];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!=-1)
{
if(a[tx][ty])
{
if(dis[tx][ty]>max(dis[x][y]+1,k-a[tx][ty]+1))dis[tx][ty]=max(dis[x][y]+1,k-a[tx][ty]+1),q.emplace(-dis[tx][ty],tx,ty);
}
else if(dis[tx][ty]>dis[x][y]+1)dis[tx][ty]=dis[x][y]+1,q.emplace(-dis[tx][ty],tx,ty);
}
}
}
unsigned long long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)if(dis[i][j]!=dis[0][0])
{
// cerr<<i<<" "<<j<<' '<<dis[i][j]<<'\n';
ans+=(unsigned long long )dis[i][j]*dis[i][j];
}
cout<<ans;
return 0;
}
/*
6 1
a?b??c
2 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 42536kb
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: 40524kb
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: 40484kb
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 ........................................................................................................#................................................................................................................................................................#................