QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628551#8236. Snake MoveAlbert711TL 8ms75960kbC++201.8kb2024-10-10 20:52:402024-10-10 20:52:48

Judging History

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

  • [2024-10-10 20:52:48]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:75960kb
  • [2024-10-10 20:52:40]
  • 提交

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
........................................................................................................#................................................................................................................................................................#................

output:


result: