QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638901#8236. Snake MoveHQLFWA 1393ms154504kbC++204.2kb2024-10-13 17:15:572024-10-13 17:16:01

Judging History

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

  • [2024-10-13 17:16:01]
  • 评测
  • 测评结果:WA
  • 用时:1393ms
  • 内存:154504kb
  • [2024-10-13 17:15:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ldb=long double;
using i128=__int128;
const ll maxn=4e5+50;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=998244353;

struct node
{
    ll w;
    ll x,y;
    bool operator<(const node &t)const
    {
        return w>t.w;
    }
};

ll vis[3010][3010];
char a[3010][3010];
ll f[3010][3010];
ll dx[10]={0,0,-1,1};
ll dy[10]={-1,1,0,0,};
void solve()
{
    ll n,m,k;
    cin>>n>>m>>k;
    pair<ll,ll> snk[k+10];
    for(ll i=1;i<=k;i++)
    {
        cin>>snk[i].first>>snk[i].second;
    }
    for(ll i=0;i<=3005;i++)
    {
        for(ll j=0;j<=3005;j++)
        {
            vis[i][j]=0;
            f[i][j]=inf;
            a[i][j]=0;
        }
    }



    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }

    ll ci=max(0ll,k-2);
    priority_queue<node>q;
    node t;
    t.w=ci;
    t.x=snk[1].first;
    t.y=snk[1].second;
    q.push(t);
    f[t.x][t.y]=ci;
    while(!q.empty())
    {
        node tp=q.top();
        q.pop();
        ll w=tp.w;
        ll x=tp.x;
        ll y=tp.y;
        if(vis[x][y]==1)continue;
        vis[x][y]=1;
        for(ll i=0;i<=3;i++)
        {
            ll tx=x+dx[i];
            ll ty=y+dy[i];
            if(f[tx][ty]>f[x][y]+1&&a[tx][ty]=='.')
            {
                f[tx][ty]=f[x][y]+1;
                if(vis[tx][ty]==0)
                {
                    t.w=f[tx][ty];
                    t.x=tx;
                    t.y=ty;
                    q.push(t);
                }
            }
        }
    }
    f[snk[1].first][snk[1].second]=0;
    for(ll i=1;i<=k-1;i++)
    {
        ll x=snk[i].first;
        ll y=snk[i].second;
        a[x][y]='#';
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            vis[i][j]=0;
        }
    }

    t.w=0;
    t.x=snk[1].first;
    t.y=snk[1].second;
    q.push(t);
    while(!q.empty())
    {
        node tp=q.top();
        q.pop();
        ll w=tp.w;
        ll x=tp.x;
        ll y=tp.y;
        if(vis[x][y]==1)continue;
        vis[x][y]=1;
        for(ll i=0;i<=3;i++)
        {
            ll tx=x+dx[i];
            ll ty=y+dy[i];
            if(f[tx][ty]>f[x][y]+1&&a[tx][ty]=='.')
            {
                f[tx][ty]=f[x][y]+1;
                if(vis[tx][ty]==0)
                {
                    t.w=f[tx][ty];
                    t.x=tx;
                    t.y=ty;
                    q.push(t);
                }
            }
        }
    }






    for(ll i=k-1;i>=2;i--)
    {
        ll x=snk[i].first;
        ll y=snk[i].second;
        ll w=ci+(i-1);
        for(ll j=0;j<=3;j++)
        {
            ll tx=x+dx[j];
            ll ty=y+dy[j];
            ll tw=k-i;
            if(a[tx][ty]=='.'&&f[tx][ty]!=inf)
            {
                ll cha=tw-f[tx][ty];
                cha=max(0ll,cha);
                ll ttw=f[tx][ty]+cha+1;
                w=min(w,ttw);
            }
        }
        f[x][y]=w;
        a[x][y]='.';
    }

    for(ll i=1;i<=k;i++)
    {
        ll x=snk[i].first;
        ll y=snk[i].second;
        a[x][y]='*';
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            if(f[i][j]!=inf&&a[i][j]=='.')
            {
                f[i][j]=min({f[i][j],f[i][j-1]+1,f[i][j+1]+1,f[i-1][j]+1,f[i+1][j]+1});
            }
        }
    }


//    for(ll i=1;i<=n;i++)
//    {
//        for(ll j=1;j<=m;j++)
//        {
//            if(f[i][j]==inf)
//            {
//                printf("  inf");
//            }
//            else printf("%4lld",f[i][j]);
//        }
//        printf("\n");
//    }
//    printf("\n");


    ull ans=0;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            if(f[i][j]==inf)ans+=0;
            else ans+=(f[i][j]*f[i][j]);
        }
    }
    printf("%llu\n",ans);



}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    ll _=1;
//    cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 154140kb

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: 12ms
memory: 154076kb

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: 4ms
memory: 154092kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 755ms
memory: 154504kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 733ms
memory: 154252kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 84ms
memory: 154116kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 76ms
memory: 154148kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 1393ms
memory: 154288kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803413395762

result:

wrong answer 1st lines differ - expected: '49803365625286', found: '49803413395762'