QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#29393#411. Dangerous SkatingETK100 ✓84ms26644kbC++232.0kb2022-04-17 17:21:282024-07-05 05:48:35

Judging History

This is the latest submission verdict.

  • [2024-07-05 05:48:35]
  • Judged
  • Verdict: 100
  • Time: 84ms
  • Memory: 26644kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-17 17:21:28]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1007,d[4][2]={{1,0},{0,1},{-1,0},{0,-1}},inf=1e9;
int n,m,r1,c1,r2,c2,dis[N][N];
int A[N][N],W[N][N],S[N][N],D[N][N];
bool vis[N][N];
char Map[N][N];
queue <pii> q;
void upd(int x,int y,int d){
    if(Map[x][y]=='.'&&d<dis[x][y]){
        dis[x][y]=d;
        if(!vis[x][y]){
            vis[x][y]=1;
            q.push({x,y});
        }
    }
}
void bfs(){
    dis[r1][c1]=0,vis[r1][c1]=1;
    q.push({r1,c1});
    while(!q.empty()){
        int x=q.front().fi,y=q.front().se;
        int Dis=dis[x][y];
        q.pop();
        //反复横跳
        rep(i,0,3){
            int nx=x+d[i][0],ny=y+d[i][1];
            upd(nx,ny,Dis+2);
        }
        //直接走
        upd(x,A[x][y]+1,Dis+1);upd(x,D[x][y]-1,Dis+1);
        upd(W[x][y]+1,y,Dis+1);upd(S[x][y]-1,y,Dis+1);
        vis[x][y]=0;
    }
}
int main(){
    n=read(),m=read();
    rep(i,1,n){
        scanf("%s",Map[i]+1);
        rep(j,1,m)dis[i][j]=inf;
    }
    rep(i,1,n){
        rep(j,1,m){
            if(Map[i][j]=='#')A[i][j]=j;
            else A[i][j]=A[i][j-1];
        }
        per(j,m,1){
            if(Map[i][j]=='#')D[i][j]=j;
            else D[i][j]=D[i][j+1];
        }
    }
    rep(j,1,m){
        rep(i,1,n){
            if(Map[i][j]=='#')W[i][j]=i;
            else W[i][j]=W[i-1][j];
        }
        per(i,n,1){
            if(Map[i][j]=='#')S[i][j]=i;
            else S[i][j]=S[i+1][j];
        }
    }
    r1=read(),c1=read(),r2=read(),c2=read();
    bfs();
    printf("%d\n",dis[r2][c2]==inf?-1:dis[r2][c2]);
    return 0;
}	

详细

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 0ms
memory: 14272kb

input:

10 10
##########
#....#.###
#.......##
#........#
#.......##
##.......#
#.......##
#.....#.##
#.....#..#
##########
4 7
8 5

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 2ms
memory: 14040kb

input:

10 10
##########
#.....#.##
#....#...#
#..#....##
#........#
#.#......#
#...##.#.#
#........#
#..#.....#
##########
9 9
9 8

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 2ms
memory: 14248kb

input:

10 10
##########
#..#.....#
#....#.#.#
##..#.##.#
##......##
##.#...#.#
#..#.##..#
#..###...#
##...#..##
##########
4 9
5 6

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 0ms
memory: 14020kb

input:

10 10
##########
##.#######
##.#.##.##
##.###.###
#.....#.##
#####..###
######...#
##....##.#
###.###.##
##########
8 9
4 3

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 2ms
memory: 13976kb

input:

10 10
##########
#.#.#....#
##..#....#
#...####.#
#.##.#..##
##..##..##
#..##..#.#
#.#....#.#
#....#...#
##########
4 9
2 2

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 14012kb

input:

10 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
##########
4 4
7 7

output:

10

result:

ok single line: '10'

Test #7:

score: 0
Accepted
time: 1ms
memory: 14112kb

input:

10 6
######
#....#
#....#
#....#
#....#
#....#
#....#
#....#
#....#
######
3 3
8 4

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 0ms
memory: 14308kb

input:

10 9
#########
##.....##
#.......#
#.......#
#....#..#
#.....#.#
#..#..#.#
#.#####.#
#.#....##
#########
5 4
9 5

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 2ms
memory: 14016kb

input:

10 10
##########
#..#.....#
#...##.#.#
#....#...#
#...#.#.##
#......#.#
#.......##
#...#..#.#
#......#.#
##########
2 3
2 3

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 14040kb

input:

10 10
##########
###......#
#..#...#.#
#....#...#
##......##
#........#
#..#...#.#
#.#.....##
#.....##.#
##########
2 9
5 4

output:

7

result:

ok single line: '7'

Subtask #2:

score: 65
Accepted

Test #11:

score: 65
Accepted
time: 0ms
memory: 20312kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

69

result:

ok single line: '69'

Test #12:

score: 0
Accepted
time: 4ms
memory: 14252kb

input:

200 200
########################################################################################################################################################################################################
#....................................................................................#........

output:

27

result:

ok single line: '27'

Test #13:

score: 0
Accepted
time: 5ms
memory: 22684kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................#...............

output:

12

result:

ok single line: '12'

Test #14:

score: 0
Accepted
time: 0ms
memory: 24284kb

input:

200 200
########################################################################################################################################################################################################
#......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......

output:

42

result:

ok single line: '42'

Test #15:

score: 0
Accepted
time: 3ms
memory: 14200kb

input:

200 200
########################################################################################################################################################################################################
#.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 5ms
memory: 20848kb

input:

200 200
########################################################################################################################################################################################################
#...#.............##.#................................................#.#.....................

output:

28

result:

ok single line: '28'

Test #17:

score: 0
Accepted
time: 4ms
memory: 14408kb

input:

200 200
########################################################################################################################################################################################################
#.........#.......#............#...........#...#.............#.......................#........

output:

390

result:

ok single line: '390'

Test #18:

score: 0
Accepted
time: 4ms
memory: 16544kb

input:

200 200
########################################################################################################################################################################################################
#.....#.......................................#....................#...#........#....#........

output:

501

result:

ok single line: '501'

Test #19:

score: 0
Accepted
time: 5ms
memory: 24296kb

input:

200 200
########################################################################################################################################################################################################
#.........##.....#..........#.#..............##..#................#..................#........

output:

82

result:

ok single line: '82'

Test #20:

score: 0
Accepted
time: 4ms
memory: 16728kb

input:

190 200
########################################################################################################################################################################################################
#.............................................................................................

output:

110

result:

ok single line: '110'

Test #21:

score: 0
Accepted
time: 3ms
memory: 16348kb

input:

200 200
########################################################################################################################################################################################################
#..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....

output:

25350

result:

ok single line: '25350'

Test #22:

score: 0
Accepted
time: 0ms
memory: 18292kb

input:

200 195
###################################################################################################################################################################################################
#..................................................................................................

output:

12813

result:

ok single line: '12813'

Test #23:

score: 0
Accepted
time: 0ms
memory: 20644kb

input:

200 200
########################################################################################################################################################################################################
#....#....................#..#......#............#................#........#..................

output:

134

result:

ok single line: '134'

Test #24:

score: 0
Accepted
time: 0ms
memory: 14432kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

191

result:

ok single line: '191'

Test #25:

score: 0
Accepted
time: 5ms
memory: 14400kb

input:

200 200
########################################################################################################################################################################################################
#....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....

output:

330

result:

ok single line: '330'

Test #26:

score: 0
Accepted
time: 0ms
memory: 24504kb

input:

200 200
########################################################################################################################################################################################################
#.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........

output:

408

result:

ok single line: '408'

Subtask #3:

score: 22
Accepted

Test #27:

score: 22
Accepted
time: 49ms
memory: 25632kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

126

result:

ok single line: '126'

Test #28:

score: 0
Accepted
time: 50ms
memory: 26140kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

81

result:

ok single line: '81'

Test #29:

score: 0
Accepted
time: 64ms
memory: 26644kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

9

result:

ok single line: '9'

Test #30:

score: 0
Accepted
time: 72ms
memory: 25968kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

46

result:

ok single line: '46'

Test #31:

score: 0
Accepted
time: 16ms
memory: 24844kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 38ms
memory: 25544kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

1994

result:

ok single line: '1994'

Test #33:

score: 0
Accepted
time: 22ms
memory: 24420kb

input:

500 500
####################################################################################################################################################################################################################################################################################################...

output:

433

result:

ok single line: '433'

Test #34:

score: 0
Accepted
time: 31ms
memory: 25260kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

675

result:

ok single line: '675'

Test #35:

score: 0
Accepted
time: 59ms
memory: 25728kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

506

result:

ok single line: '506'

Test #36:

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

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

319

result:

ok single line: '319'

Test #37:

score: 0
Accepted
time: 32ms
memory: 25736kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

1141

result:

ok single line: '1141'

Test #38:

score: 0
Accepted
time: 55ms
memory: 25984kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

99

result:

ok single line: '99'

Test #39:

score: 0
Accepted
time: 35ms
memory: 25548kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

660018

result:

ok single line: '660018'

Test #40:

score: 0
Accepted
time: 12ms
memory: 25552kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

332551

result:

ok single line: '332551'

Extra Test:

score: 0
Extra Test Passed