QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799330#5514. Mazesichengzhou0 3ms16156kbC++174.0kb2024-12-05 11:04:592024-12-05 11:04:59

Judging History

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

  • [2024-12-05 11:04:59]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:16156kb
  • [2024-12-05 11:04:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=6e6+6;
#define mkp make_pair
vector<string>a;
string str;
int R,C,n,Sr,Sc,Gr,Gc;
int q[N];
#define id(x,y) ((x-1)*C+(y-1))
#define mid (l+r)/2
#define mi (i+j)/2
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int d[N];
int c[N<<2],s[4][N<<2],rt,tot,hh,tt;
int x,y,u,v,V;
void upd(int p)
{
    c[p]=0;
    for(int i=0;i<4;i++)
    {
        c[p]+=c[s[i][p]];
    }
}
void init(int& p,int l,int r,int i,int j)
{
    if(l>r||i>j)
    {
        return ;
    }
    p=++tot;
//    printf("init(%d,%d,%d,%d,%d)\n",p,l,r,i,j);
    if(l==r&&i==j)
    {
        c[p]=1;
        return ;
    }
    init(s[0][p],l,mid,i,mi);
    init(s[1][p],l,mid,mi+1,j);
    init(s[2][p],mid+1,r,i,mi);
    init(s[3][p],mid+1,r,mi+1,j);
    upd(p);
}
void erase(int p,int l,int r,int i,int j)
{
    if(r<x||y<l||j<u||v<i||l>r||i>j||c[p]==0)
    {
        return;
    }
    if(l==r&&i==j)
    {
        c[p]=0;
        return ;
    }
    erase(s[0][p],l,mid,i,mi);
    erase(s[1][p],l,mid,mi+1,j);
    erase(s[2][p],mid+1,r,i,mi);
    erase(s[3][p],mid+1,r,mi+1,j);
    upd(p);
}
void query(int p,int l,int r,int i,int j)
{
    if(r<x||y<l||j<u||v<i||l>r||i>j||c[p]==0)
    {
        return;
    }
//    printf("query(%d,%d,%d,%d,%d)\n",p,l,r,i,j);
    if(l==r&&i==j)
    {
        if((l==x||l==y)&&(i==u||i==v))
        {
            return ;
        }
    //    cout<<V<<' '<<l<<' '<<i<<'\n';
        d[id(l,i)]=d[V]+1;
        q[++tt]=id(l,i);
        c[p]=0;
        return ;
    }
    query(s[0][p],l,mid,i,mi);
    query(s[1][p],l,mid,mi+1,j);
    query(s[2][p],mid+1,r,i,mi);
    query(s[3][p],mid+1,r,mi+1,j);
    upd(p);
}
int main()
{
    cin>>R>>C>>n>>Sr>>Sc>>Gr>>Gc;
    auto get=[&](int id){
        return mkp(id/C+1,id%C+1);
    };
    a.push_back(" ");
    for(int i=1;i<=R;i++)
    {
        cin>>str;str=" "+str;
        a.push_back(str);
    }
    init(rt,1,R,1,C);
    hh=1,tt=0;
    q[++tt]=id(Sr,Sc);
    for(int i=0;i<R*C;i++)
    {
        d[i]=-1;
    }
    d[id(Sr,Sc)]=0;
    x=y=Sr;u=v=Sc;
    erase(1,1,R,1,C);
    while(hh<=tt)
    {
        for(int i=hh;i<=tt;i++)
        {
        auto [l,r]=get(q[i]);
        for(int k=0;k<4;k++)
        {
            int tx=l+dx[k],ty=r+dy[k];
            if(tx<1||tx>R||ty<1||ty>C)
            {
                continue;
            }
            if(a[tx][ty]=='.'&&d[id(tx,ty)]==-1)
            {
            //pr    cout<<tt<<' '<<tx<<' '<<ty<<a[tx][ty]<<'\n';
                d[id(tx,ty)]=d[q[i]];
                x=y=tx;u=v=ty;
                erase(1,1,R,1,C);
                q[++tt]=id(tx,ty);
            }
        }
        }
    //    cout<<hh<<'*'<<tt<<'\n';
        int cur=tt;
        while(hh<=cur)
        {
        auto [l,r]=get(q[hh]);
        x=l-n;y=l+n;u=r-n;v=r+n;V=d[q[hh]];
        query(1,1,R,1,C);
        hh++;
        continue;
        if(R*C<=1000)
        {
        for(int tx=1;tx<=R;tx++)
        {
            for(int ty=1;ty<=C;ty++)
            {
                if(abs(tx-x)+abs(ty-y)<=2*n-1&&abs(tx-x)<=n&&abs(ty-y)<=n)
                {
                    if(d[id(tx,ty)]==-1)
            {
                d[id(tx,ty)]=d[q[hh]]+1;
            //    cout<<tt<<' '<<x<<' '<<y<<' '<<tx<<' '<<ty<<'\n';
                q[++tt]=id(tx,ty);
            }
                }
            }
        }
        hh++;
        continue;
        }
        for(int k=0;k<4;k++)
        {
            int tx=x+dx[k],ty=y+dy[k];
            if(tx<1||tx>R||ty<1||ty>C)
            {
                continue;
            }
            if(d[id(tx,ty)]==-1)
            {
                d[id(tx,ty)]=d[q[hh]]+1;
            //    cout<<tt<<' '<<x<<' '<<y<<' '<<tx<<' '<<ty<<'\n';
                q[++tt]=id(tx,ty);
            }
        }
    //    cout<<hh<<' '<<x<<' '<<y<<' '<<d[id(x,y)]<<endl;
        hh++;
        }
    }
    cout<<d[id(Gr,Gc)]<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 16156kb

input:

31 32 1
25 22
5 3
################################
################################
.###############################
.###############################
##..###############.############
###.###############.############
#####.##########################
###.#.##########################
###.##############...

output:

0

result:

wrong answer 1st lines differ - expected: '26', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #52:

score: 19
Accepted
time: 0ms
memory: 11800kb

input:

3 6 2
2 1
3 3
...###
..##..
#..###

output:

0

result:

ok single line: '0'

Test #53:

score: 19
Accepted
time: 2ms
memory: 11804kb

input:

4 24 4
3 4
3 3
..#...##.#...###...###.#
.##.#..##.##.##..#.####.
#.......#.#.#...#.#####.
######....######.#...#.#

output:

0

result:

ok single line: '0'

Test #54:

score: 0
Wrong Answer
time: 0ms
memory: 11864kb

input:

2 136 2
1 133
2 45
#############################################.##################.#.#######.##############.#################.##############.##.######.###
####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################

output:

0

result:

wrong answer 1st lines differ - expected: '41', found: '0'

Subtask #3:

score: 0
Wrong Answer

Test #64:

score: 0
Wrong Answer
time: 3ms
memory: 15820kb

input:

35 60 20
3 60
2 44
.#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####.
#.#......#.####..####...#...#......#........####....##.#.###
.#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##.
.#.#...##..#.##.......#......##......####...##.##..##.#....#
#...#.......#..#..#...#.#####.##.###....

output:

0

result:

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

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%