QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376310#8236. Snake Moveir101WA 1ms8124kbC++201.8kb2024-04-04 03:40:392024-04-04 03:40:39

Judging History

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

  • [2024-04-04 03:40:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8124kb
  • [2024-04-04 03:40:39]
  • 提交

answer

# pragma GCC optimize(2)
#include <iostream>
#include <queue>
const int mod=1e9+7;
#define ll long long

using namespace std;
#define  endl '\n'
//learning
#define PII pair<int,int>
const int N=3e3+5;
int f[N][N];
int extra_dis[N][N];
char g[N][N];
int n,m,k;
int stx,sty;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
void solve(){
    scanf("%d %d %d",&n,&m,&k);

    for (int i = 1; i <=k ; ++i) {
        int x,y;
        scanf("%d %d",&x,&y);
        if(i==1){
            stx=x,sty=y;
        }
        extra_dis[x][y]=k-i;
    }
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=m ; ++j) {
            scanf("%c",&g[i][j]);
            f[i][j]=1e9;
        }
    }
    queue<PII>q;
    q.push({stx,sty});
    f[stx][sty]=0;
    while (!q.empty()){
        auto [x,y]=q.front();
        q.pop();
        for (int i = 0; i <4 ; ++i) {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1 or xx>n or yy<1 or yy>m or g[xx][yy]=='#')continue;
            if(!extra_dis[xx][yy]){
                if(f[xx][yy]>f[x][y]+1){
                    f[xx][yy]=f[x][y]+1;
                    q.push({xx,yy});
                }
            }
            else{
                if(f[xx][yy]>f[x][y]+max(0,extra_dis[xx][yy]-f[x][y])+1) {
                    f[xx][yy] = f[x][y] + max(0, extra_dis[xx][yy] - f[x][y]) + 1;
                    q.push({xx, yy});
                }

            }
        }
    }
    unsigned ll ans=0;
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=m ; ++j) {
            if(f[i][j]==1e9){
                continue;
            }
            ans+=(unsigned ll)f[i][j]*f[i][j];
        }
    }
    printf("%lld",ans);




}
int32_t main() {
    int t=1;
    while (t--){
        solve();
    }
}

詳細信息

Test #1:

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

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: 8124kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 7876kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

218

result:

wrong answer 1st lines differ - expected: '407', found: '218'