QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100575 | #411. Dangerous Skating | lmeowdn | 100 ✓ | 507ms | 134124kb | C++14 | 1.8kb | 2023-04-26 20:16:10 | 2023-04-26 20:16:13 |
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 fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1009,inf=0x3f3f3f3f;
int n,m,sx,sy,tx,ty,vst[N*N],id[N][N],tot,p[N][N][4],d[N*N];
char s[N][N];
vp e[N*N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dijkstra(int s,int t) {
priority_queue<pii>q; q.push(pii(0,s));
memset(d,0x3f,sizeof(d)); d[s]=0;
while(!q.empty()) {
int u=q.top().se; q.pop();
if(vst[u]) continue; vst[u]=1;
for(auto [v,w]:e[u]) if(d[v]>d[u]+w)
d[v]=d[u]+w, q.push(pii(-d[v],v));
} return d[t];
}
signed main() {
n=read(), m=read();
rep(i,1,n) scanf("%s",s[i]+1);
sx=read(), sy=read(), tx=read(), ty=read();
rep(i,1,n) rep(j,1,m) if(s[i][j]=='.') id[i][j]=++tot;
rep(i,1,n) rep(j,1,m) if(id[i][j]) {
rep(k,0,3) if(id[i+dx[k]][j+dy[k]])
e[id[i][j]].eb(id[i+dx[k]][j+dy[k]],2);
}
per(i,n,1) per(j,m,1) if(id[i][j]) {
rep(k,0,1) {
if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
e[id[i][j]].eb(p[i][j][k],1);
}
}
rep(i,1,n) rep(j,1,m) if(id[i][j]) {
rep(k,2,3) {
if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
e[id[i][j]].eb(p[i][j][k],1);
}
}
if(!id[sx][sy]||!id[tx][ty]) return puts("-1"), 0;
int res=dijkstra(id[sx][sy],id[tx][ty]);
if(res==inf) puts("-1"); else printf("%d\n",res);
return 0;
}
详细
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 2ms
memory: 34344kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 34348kb
input:
10 10 ########## #.....#.## #....#...# #..#....## #........# #.#......# #...##.#.# #........# #..#.....# ########## 9 9 9 8
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 3ms
memory: 33740kb
input:
10 10 ########## #..#.....# #....#.#.# ##..#.##.# ##......## ##.#...#.# #..#.##..# #..###...# ##...#..## ########## 4 9 5 6
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 3ms
memory: 34460kb
input:
10 10 ########## ##.####### ##.#.##.## ##.###.### #.....#.## #####..### ######...# ##....##.# ###.###.## ########## 8 9 4 3
output:
10
result:
ok single line: '10'
Test #5:
score: 0
Accepted
time: 4ms
memory: 33912kb
input:
10 10 ########## #.#.#....# ##..#....# #...####.# #.##.#..## ##..##..## #..##..#.# #.#....#.# #....#...# ########## 4 9 2 2
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 33628kb
input:
10 10 ########## #........# #........# #........# #........# #........# #........# #........# #........# ########## 4 4 7 7
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 0ms
memory: 32860kb
input:
10 6 ###### #....# #....# #....# #....# #....# #....# #....# #....# ###### 3 3 8 4
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 0ms
memory: 34080kb
input:
10 9 ######### ##.....## #.......# #.......# #....#..# #.....#.# #..#..#.# #.#####.# #.#....## ######### 5 4 9 5
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 4ms
memory: 33208kb
input:
10 10 ########## #..#.....# #...##.#.# #....#...# #...#.#.## #......#.# #.......## #...#..#.# #......#.# ########## 2 3 2 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 33680kb
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: 11ms
memory: 42160kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
69
result:
ok single line: '69'
Test #12:
score: 0
Accepted
time: 18ms
memory: 41808kb
input:
200 200 ######################################################################################################################################################################################################## #....................................................................................#........
output:
27
result:
ok single line: '27'
Test #13:
score: 0
Accepted
time: 18ms
memory: 39952kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................#...............
output:
12
result:
ok single line: '12'
Test #14:
score: 0
Accepted
time: 12ms
memory: 40772kb
input:
200 200 ######################################################################################################################################################################################################## #......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......
output:
42
result:
ok single line: '42'
Test #15:
score: 0
Accepted
time: 8ms
memory: 39460kb
input:
200 200 ######################################################################################################################################################################################################## #.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 18ms
memory: 41272kb
input:
200 200 ######################################################################################################################################################################################################## #...#.............##.#................................................#.#.....................
output:
28
result:
ok single line: '28'
Test #17:
score: 0
Accepted
time: 19ms
memory: 39140kb
input:
200 200 ######################################################################################################################################################################################################## #.........#.......#............#...........#...#.............#.......................#........
output:
390
result:
ok single line: '390'
Test #18:
score: 0
Accepted
time: 13ms
memory: 40400kb
input:
200 200 ######################################################################################################################################################################################################## #.....#.......................................#....................#...#........#....#........
output:
501
result:
ok single line: '501'
Test #19:
score: 0
Accepted
time: 20ms
memory: 39548kb
input:
200 200 ######################################################################################################################################################################################################## #.........##.....#..........#.#..............##..#................#..................#........
output:
82
result:
ok single line: '82'
Test #20:
score: 0
Accepted
time: 7ms
memory: 40940kb
input:
190 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
110
result:
ok single line: '110'
Test #21:
score: 0
Accepted
time: 7ms
memory: 40252kb
input:
200 200 ######################################################################################################################################################################################################## #..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....
output:
25350
result:
ok single line: '25350'
Test #22:
score: 0
Accepted
time: 10ms
memory: 39820kb
input:
200 195 ################################################################################################################################################################################################### #..................................................................................................
output:
12813
result:
ok single line: '12813'
Test #23:
score: 0
Accepted
time: 14ms
memory: 38812kb
input:
200 200 ######################################################################################################################################################################################################## #....#....................#..#......#............#................#........#..................
output:
134
result:
ok single line: '134'
Test #24:
score: 0
Accepted
time: 11ms
memory: 41032kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
191
result:
ok single line: '191'
Test #25:
score: 0
Accepted
time: 10ms
memory: 38644kb
input:
200 200 ######################################################################################################################################################################################################## #....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....
output:
330
result:
ok single line: '330'
Test #26:
score: 0
Accepted
time: 11ms
memory: 38708kb
input:
200 200 ######################################################################################################################################################################################################## #.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........
output:
408
result:
ok single line: '408'
Subtask #3:
score: 22
Accepted
Test #27:
score: 22
Accepted
time: 449ms
memory: 134124kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
126
result:
ok single line: '126'
Test #28:
score: 0
Accepted
time: 480ms
memory: 134112kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
81
result:
ok single line: '81'
Test #29:
score: 0
Accepted
time: 507ms
memory: 133684kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
9
result:
ok single line: '9'
Test #30:
score: 0
Accepted
time: 372ms
memory: 127140kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
46
result:
ok single line: '46'
Test #31:
score: 0
Accepted
time: 145ms
memory: 93400kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
-1
result:
ok single line: '-1'
Test #32:
score: 0
Accepted
time: 399ms
memory: 133928kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1994
result:
ok single line: '1994'
Test #33:
score: 0
Accepted
time: 72ms
memory: 62292kb
input:
500 500 ####################################################################################################################################################################################################################################################################################################...
output:
433
result:
ok single line: '433'
Test #34:
score: 0
Accepted
time: 256ms
memory: 123636kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
675
result:
ok single line: '675'
Test #35:
score: 0
Accepted
time: 352ms
memory: 132768kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
506
result:
ok single line: '506'
Test #36:
score: 0
Accepted
time: 321ms
memory: 124964kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
319
result:
ok single line: '319'
Test #37:
score: 0
Accepted
time: 220ms
memory: 111700kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1141
result:
ok single line: '1141'
Test #38:
score: 0
Accepted
time: 504ms
memory: 133628kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
99
result:
ok single line: '99'
Test #39:
score: 0
Accepted
time: 211ms
memory: 106588kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
660018
result:
ok single line: '660018'
Test #40:
score: 0
Accepted
time: 64ms
memory: 79640kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
332551
result:
ok single line: '332551'
Extra Test:
score: 0
Extra Test Passed