QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628551 | #8236. Snake Move | Albert711 | TL | 8ms | 75960kb | C++20 | 1.8kb | 2024-10-10 20:52:40 | 2024-10-10 20:52:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db double
const int mod=1e9+7;
const int N=3e3+5;
int pic[N][N];
int ans[N][N];
int mx[4]={-1,1,0,0};
int my[4]={0,0,-1,1};
void abt(){
int n,m,k;
cin>>n>>m>>k;
int sx,sy;
for(int i=1;i<=k;i++){
int t1,t2;
cin>>t1>>t2;
if(i==1){
sx=t1;
sy=t2;
}
pic[t1][t2]=k-i+1;
}
for(int i=1;i<=n;i++){
string s;
cin>>s;
s=' '+s;
for(int j=1;j<=m;j++){
if(s[j]=='#'){
pic[i][j]=-1;
}
}
}
memset(ans,0x3f,sizeof(ans));
queue<array<int,3>>q;
q.push({sx,sy,0});
pic[sx][sy]=0;
while(!q.empty()){
auto t=q.front();
int x=t[0],y=t[1],st=t[2];
q.pop();
int tot=max(st,pic[x][y]);
if(tot>ans[x][y]){
continue;
}else{
ans[x][y]=tot;
for(int i=0;i<4;i++){
int xx=x+mx[i];
int yy=y+my[i];
if(xx<1||xx>n||yy<1||yy>m||pic[xx][yy]==-1) continue;
q.push({xx,yy,tot+1});
}
}
}
unsigned long long out=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ans[i][j]==4557430888798830399) continue;
out=out+ans[i][j]*ans[i][j];
}
}
cout<<out<<'\n';
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<ans[i][j]<<" \n"[j==m];
// }
// }
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--) abt();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 75740kb
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: 4ms
memory: 75960kb
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: 8ms
memory: 75904kb
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 ........................................................................................................#................................................................................................................................................................#................