QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123781 | #411. Dangerous Skating | Faccirx | 100 ✓ | 1891ms | 176396kb | C++20 | 1.9kb | 2023-07-13 16:58:01 | 2023-07-13 16:58:04 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
constexpr int inf=2e18;
constexpr double eps=1e-8;
template<class T>
constexpr bool chkmax(T &a,T b){
if(a<b) return a=b,true;
return false;
}
template<class T>
constexpr bool chkmin(T &a,T b){
if(a>b) return a=b,true;
return false;
}
class Graph{
private:
int n;
std::vector<std::vector<std::pair<int,int>>>_adj;
public:
Graph(int n):n(n),_adj(n){}
void add_edge(int u,int v,int w){
_adj[u].emplace_back(v,w);
}
void add_biedge(int u,int v,int w){
add_edge(u,v,w);
add_edge(v,u,w);
}
std::vector<std::pair<int,int>>adj(int i)const{
return _adj[i];
}
int deg(int i)const{
return _adj[i].size();
}
int size()const{
return n;
}
};
void solve(){
int n,m;
std::cin>>n>>m;
std::vector<std::string>a(n);
for(int i=0;i<n;i++){
std::cin>>a[i];
}
int sx,sy,tx,ty;
std::cin>>sx>>sy>>tx>>ty;
sx--,sy--,tx--,ty--;
auto id=[&](int x,int y){
return x*m+y;
};
Graph G(n*m);
std::vector<int>dx={1,-1,0,0},dy={0,0,1,-1};
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
if(a[x][y]=='#'){
continue;
}
for(int i=0;i<4;i++){
int nx=x,ny=y;
while(a[nx+dx[i]][ny+dy[i]]=='.'){
nx+=dx[i],ny+=dy[i];
}
G.add_edge(id(x,y),id(nx,ny),1);
int vx=x+dx[i],vy=y+dy[i];
G.add_edge(id(x,y),id(vx,vy),2);
}
}
}
std::vector<int>dist(n*m,inf);
dist[id(sx,sy)]=0;
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>>h;
h.emplace(0,id(sx,sy));
while(!h.empty()){
auto[d,u]=h.top();
h.pop();
if(dist[u]!=d){
continue;
}
for(auto[v,w]:G.adj(u)){
if(chkmin(dist[v],dist[u]+w)){
h.emplace(dist[v],v);
}
}
}
int ans=dist[id(tx,ty)];
if(ans==inf){
ans=-1;
}
std::cout<<ans<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
solve();
return 0;
}
詳細信息
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 0ms
memory: 3456kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
10 10 ########## #.....#.## #....#...# #..#....## #........# #.#......# #...##.#.# #........# #..#.....# ########## 9 9 9 8
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
10 10 ########## #..#.....# #....#.#.# ##..#.##.# ##......## ##.#...#.# #..#.##..# #..###...# ##...#..## ########## 4 9 5 6
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
10 10 ########## ##.####### ##.#.##.## ##.###.### #.....#.## #####..### ######...# ##....##.# ###.###.## ########## 8 9 4 3
output:
10
result:
ok single line: '10'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
10 10 ########## #.#.#....# ##..#....# #...####.# #.##.#..## ##..##..## #..##..#.# #.#....#.# #....#...# ########## 4 9 2 2
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
10 10 ########## #........# #........# #........# #........# #........# #........# #........# #........# ########## 4 4 7 7
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
10 6 ###### #....# #....# #....# #....# #....# #....# #....# #....# ###### 3 3 8 4
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
10 9 ######### ##.....## #.......# #.......# #....#..# #.....#.# #..#..#.# #.#####.# #.#....## ######### 5 4 9 5
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
10 10 ########## #..#.....# #...##.#.# #....#...# #...#.#.## #......#.# #.......## #...#..#.# #......#.# ########## 2 3 2 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3500kb
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: 25ms
memory: 9896kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
69
result:
ok single line: '69'
Test #12:
score: 0
Accepted
time: 23ms
memory: 10104kb
input:
200 200 ######################################################################################################################################################################################################## #....................................................................................#........
output:
27
result:
ok single line: '27'
Test #13:
score: 0
Accepted
time: 19ms
memory: 10016kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................#...............
output:
12
result:
ok single line: '12'
Test #14:
score: 0
Accepted
time: 10ms
memory: 8724kb
input:
200 200 ######################################################################################################################################################################################################## #......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......
output:
42
result:
ok single line: '42'
Test #15:
score: 0
Accepted
time: 1ms
memory: 6988kb
input:
200 200 ######################################################################################################################################################################################################## #.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 18ms
memory: 9876kb
input:
200 200 ######################################################################################################################################################################################################## #...#.............##.#................................................#.#.....................
output:
28
result:
ok single line: '28'
Test #17:
score: 0
Accepted
time: 9ms
memory: 8836kb
input:
200 200 ######################################################################################################################################################################################################## #.........#.......#............#...........#...#.............#.......................#........
output:
390
result:
ok single line: '390'
Test #18:
score: 0
Accepted
time: 12ms
memory: 8340kb
input:
200 200 ######################################################################################################################################################################################################## #.....#.......................................#....................#...#........#....#........
output:
501
result:
ok single line: '501'
Test #19:
score: 0
Accepted
time: 9ms
memory: 8848kb
input:
200 200 ######################################################################################################################################################################################################## #.........##.....#..........#.#..............##..#................#..................#........
output:
82
result:
ok single line: '82'
Test #20:
score: 0
Accepted
time: 19ms
memory: 9648kb
input:
190 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
110
result:
ok single line: '110'
Test #21:
score: 0
Accepted
time: 5ms
memory: 8048kb
input:
200 200 ######################################################################################################################################################################################################## #..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....
output:
25350
result:
ok single line: '25350'
Test #22:
score: 0
Accepted
time: 3ms
memory: 6208kb
input:
200 195 ################################################################################################################################################################################################### #..................................................................................................
output:
12813
result:
ok single line: '12813'
Test #23:
score: 0
Accepted
time: 13ms
memory: 8480kb
input:
200 200 ######################################################################################################################################################################################################## #....#....................#..#......#............#................#........#..................
output:
134
result:
ok single line: '134'
Test #24:
score: 0
Accepted
time: 12ms
memory: 9592kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
191
result:
ok single line: '191'
Test #25:
score: 0
Accepted
time: 11ms
memory: 8052kb
input:
200 200 ######################################################################################################################################################################################################## #....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....
output:
330
result:
ok single line: '330'
Test #26:
score: 0
Accepted
time: 6ms
memory: 8112kb
input:
200 200 ######################################################################################################################################################################################################## #.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........
output:
408
result:
ok single line: '408'
Subtask #3:
score: 22
Accepted
Test #27:
score: 22
Accepted
time: 1891ms
memory: 175804kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
126
result:
ok single line: '126'
Test #28:
score: 0
Accepted
time: 1534ms
memory: 176396kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
81
result:
ok single line: '81'
Test #29:
score: 0
Accepted
time: 729ms
memory: 176192kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
9
result:
ok single line: '9'
Test #30:
score: 0
Accepted
time: 395ms
memory: 162476kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
46
result:
ok single line: '46'
Test #31:
score: 0
Accepted
time: 77ms
memory: 105312kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
-1
result:
ok single line: '-1'
Test #32:
score: 0
Accepted
time: 1888ms
memory: 175684kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1994
result:
ok single line: '1994'
Test #33:
score: 0
Accepted
time: 87ms
memory: 40588kb
input:
500 500 ####################################################################################################################################################################################################################################################################################################...
output:
433
result:
ok single line: '433'
Test #34:
score: 0
Accepted
time: 229ms
memory: 155672kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
675
result:
ok single line: '675'
Test #35:
score: 0
Accepted
time: 495ms
memory: 173116kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
506
result:
ok single line: '506'
Test #36:
score: 0
Accepted
time: 292ms
memory: 157052kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
319
result:
ok single line: '319'
Test #37:
score: 0
Accepted
time: 160ms
memory: 133548kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1141
result:
ok single line: '1141'
Test #38:
score: 0
Accepted
time: 810ms
memory: 175244kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
99
result:
ok single line: '99'
Test #39:
score: 0
Accepted
time: 176ms
memory: 128536kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
660018
result:
ok single line: '660018'
Test #40:
score: 0
Accepted
time: 205ms
memory: 82352kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
332551
result:
ok single line: '332551'
Extra Test:
score: 0
Extra Test Passed