QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620138#8236. Snake Movegates_orzTL 1ms9996kbC++202.8kb2024-10-07 16:46:352024-10-07 16:46:37

Judging History

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

  • [2024-10-07 16:46:37]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9996kb
  • [2024-10-07 16:46:35]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("2")
#pragma GCC optimize("3")
using namespace std;

using LL = long long;
using ULL = unsigned long long;
const int N = 1e7 + 10;
int n, m;


int a[4]={-1,0,1,0};
int b[4]={0,1,0,-1};
int body[4010][4010];
LL res[4010][4010];
//string ch[3010];
char ch[4010][4010];
struct Node {
    int x,y;
    int step;
};

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

inline void write(ULL x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

Node q[N];
int hh,tt;
void solve() {
    int k;
    //cin>>n>>m>>k;
    n=read(),m=read(),k=read();
    int st_x=0,st_y=0;
    for(int i=1;i<=k;++i) {
        int x,y;
        //cin>>x>>y;
        x=read(),y=read();
        if(!st_x&&!st_y) {
            st_x=x,st_y=y;
        }
        body[x][y]=i;
    }
    for(int i=1;i<=n;++i) {
        //cin>>ch[i];
        //ch[i]=" "+ch[i];
        scanf("%s",ch[i]+1);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++)res[i][j]=1e9;
    }

    //queue<Node>q;
    res[st_x][st_y]=0;
    //q.push({st_x,st_y,0});
    hh=1;
    q[++tt]={st_x,st_y,0};
    int sign=0;
    while(hh<=tt) {
        auto [x,y,step]=q[tt];
        //q.pop();
        tt--;
        for(int i=0;i<4;i++) {
            int tx=x+a[i];
            int ty=y+b[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m) {
                if(ch[tx][ty]=='#')continue;

                if(!body[tx][ty]) {
                    if(res[tx][ty]>step+1) {
                        res[tx][ty] = step + 1;
                        //q.push({tx, ty, step + 1});
                        q[++tt]={tx,ty,step+1};
                    }
                }
                else {

                    int now=step+1;
                    if(now<k-body[tx][ty]+(body[tx][ty]!=k))now=(k-body[tx][ty]+(body[tx][ty]!=k));
                    if(res[tx][ty]>now) {
                        res[tx][ty]=now;
                        //body[tx][ty]=0;
                        //q.push({tx,ty,now});
                        q[++tt]={tx,ty,now};
                    }
                }
            }
        }
    }
    ULL ans=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(res[i][j]==1e9)continue;
            //cerr<<"i="<<i<<" j="<<j<<" res="<<res[i][j]<<"\n";
            ans+=(res[i][j]*res[i][j]);
        }
    }
    //cout<<ans<<"\n";
    write(ans);
}

signed main() {
    int T = 1;
    //cin >> T;
    while (T--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9844kb

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: 1ms
memory: 9996kb

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: 1ms
memory: 9984kb

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: