QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688071 | #8236. Snake Move | shinonomezhou | RE | 1ms | 3596kb | C++23 | 1.8kb | 2024-10-29 23:07:46 | 2024-10-29 23:07:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+10;
const ll INF=1e18;
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define fi first
#define se second
ll n,m,k;
//ll f[N][N],flag[N][N];
//bool re[N][N];
vector<vector<char> >maze(n+10,vector<char>(m+10));
vector<vector<ll> >f(n+10,vector<ll>(m+10,INF));
vector<vector<ll> >flag(n+10,vector<ll>(m+10));
vector<vector<bool> >re(n+10,vector<bool>(m+10));
//char maze[N][N];
priority_queue<plll,vector<plll>,greater<plll> >q;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
bool dead(ll x,ll y){
if(x<1||x>n||y<1||y>m||maze[x][y]=='#')return true;
else return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=INF;
for(int i=1;i<=k;i++){
// cout<<"y\n";
ll x,y;
cin>>x>>y;
flag[x][y]=k-i;
if(i==1)q.push({0,{x,y}}),f[x][y]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>maze[i][j];
}
}
while(q.size()){
plll p=q.top();
q.pop();
ll dis=p.fi;
ll tx=p.se.fi,ty=p.se.se;
if(re[tx][ty])continue;
re[tx][ty]=true;
for(int i=0;i<4;i++){
ll nx=tx+dx[i],ny=ty+dy[i];
if(dead(nx,ny))continue;
if(re[nx][ny])continue;
if(f[nx][ny]>max(dis+1,flag[nx][ny]+1)){
f[nx][ny]=max(dis+1,flag[nx][ny]+1);
q.push({f[nx][ny],{nx,ny}});
}
}
}
ll ans=0;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// if(flag[i][j]!=0)cout<<k-flag[i][j]<<' ';
// else cout<<maze[i][j]<<' ';
// }
// cout<<'\n';
// }
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<<f[i][j]<<' ';
}
// cout<<'\n';
}
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
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: 3560kb
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: 3596kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Runtime Error
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................