QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#29393 | #411. Dangerous Skating | ETK | 100 ✓ | 84ms | 26644kb | C++23 | 2.0kb | 2022-04-17 17:21:28 | 2024-07-05 05:48:35 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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