QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799293#5514. Mazesichengzhou0 1ms5924kbC++172.3kb2024-12-05 10:07:572024-12-05 10:07:57

Judging History

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

  • [2024-12-05 10:07:57]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5924kb
  • [2024-12-05 10:07:57]
  • 提交

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 s;
int R,C,n,Sr,Sc,Gr,Gc;
int q[N];
#define id(x,y) ((x-1)*C+(y-1))
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int d[N];
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>>s;s=" "+s;
        a.push_back(s);
    }
    int 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;
    while(hh<=tt)
    {
        for(int i=hh;i<=tt;i++)
        {
        auto [x,y]=get(q[i]);
        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(a[tx][ty]=='.'&&d[id(tx,ty)]==-1)
            {
            //    cout<<tt<<' '<<tx<<' '<<ty<<a[tx][ty]<<'\n';
                d[id(tx,ty)]=d[q[i]];
                q[++tt]=id(tx,ty);
            }
        }
        }
    //    cout<<hh<<'*'<<tt<<'\n';
        int cur=tt;
        while(hh<=cur)
        {
        auto [x,y]=get(q[hh]);
        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++;
        }
        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: 1ms
memory: 5924kb

input:

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

output:

35

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #52:

score: 19
Accepted
time: 1ms
memory: 5716kb

input:

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

output:

0

result:

ok single line: '0'

Test #53:

score: 19
Accepted
time: 1ms
memory: 5612kb

input:

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

output:

0

result:

ok single line: '0'

Test #54:

score: 0
Wrong Answer
time: 1ms
memory: 5684kb

input:

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

output:

42

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #64:

score: 16
Accepted
time: 1ms
memory: 5664kb

input:

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

output:

1

result:

ok single line: '1'

Test #65:

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

input:

63 602 3
10 463
3 402
#.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....

output:

23

result:

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

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%