QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#124271 | #411. Dangerous Skating | tcwxxxx | 100 ✓ | 697ms | 188636kb | C++14 | 2.3kb | 2023-07-14 15:37:47 | 2023-07-14 15:37:50 |
Judging History
answer
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
long long y,z;
};
char a[1010][1010];
vector<node>b[1000010];
long long dis[1000010];
long long fx[5]={0,0,0,1,-1};
long long fy[5]={0,1,-1,0,0};
bool vis[1000010];
void dij(long long s)
{
long long i;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<pair<long long,long long>>q;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
long long t=q.top().second;
q.pop();
if(vis[t]==1)
{
continue;
}
vis[t]=1;
for(i=0;i<b[t].size();i++)
{
long long yy=b[t][i].y,zz=b[t][i].z;
if(dis[yy]>dis[t]+zz)
{
dis[yy]=dis[t]+zz;
q.push(make_pair(-dis[yy],yy));
}
}
}
return ;
}
int main()
{
long long n,m,x,y,x1,y1,i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>x>>y>>x1>>y1;
for(i=1;i<=n;i++)
{
long long la=0;
for(j=1;j<=m;j++)
{
if(a[i][j]=='#')
{
la=j;
}
else
{
if(la!=j-1)
{
node e;
e.y=i*m+la+1-m;
e.z=1;
b[i*m+j-m].push_back(e);
}
}
}
la=0;
for(j=m;j>=1;j--)
{
if(a[i][j]=='#')
{
la=j;
}
else
{
if(la!=j+1)
{
node e;
e.y=i*m+la-1-m;
e.z=1;
b[i*m+j-m].push_back(e);
}
}
}
}
for(i=1;i<=m;i++)
{
long long la=0;
for(j=1;j<=n;j++)
{
if(a[j][i]=='#')
{
la=j;
}
else
{
if(la!=j-1)
{
node e;
e.y=la*m+i;
e.z=1;
b[j*m+i-m].push_back(e);
}
}
}
la=0;
for(j=n;j>=1;j--)
{
if(a[j][i]=='#')
{
la=j;
}
else
{
if(la!=j+1)
{
node e;
e.y=la*m+i-2*m;
e.z=1;
b[j*m+i-m].push_back(e);
}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]=='.')
{
long long xx,yy;
for(k=1;k<=4;k++)
{
xx=i+fx[k];
yy=j+fy[k];
if(xx<1||xx>n||yy<1||yy>m)
continue;
if(a[xx][yy]=='.')
{
node e;
e.y=xx*m+yy-m;
e.z=2;
b[i*m+j-m].push_back(e);
}
}
}
}
}
dij(x*m+y-m);
if(dis[x1*m+y1-m]>1e9)
{
cout<<-1;
}
else
{
cout<<dis[x1*m+y1-m];
}
return 0;
}
詳細信息
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 6ms
memory: 35908kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 10ms
memory: 36200kb
input:
10 10 ########## #.....#.## #....#...# #..#....## #........# #.#......# #...##.#.# #........# #..#.....# ########## 9 9 9 8
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 3ms
memory: 35684kb
input:
10 10 ########## #..#.....# #....#.#.# ##..#.##.# ##......## ##.#...#.# #..#.##..# #..###...# ##...#..## ########## 4 9 5 6
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 1ms
memory: 35692kb
input:
10 10 ########## ##.####### ##.#.##.## ##.###.### #.....#.## #####..### ######...# ##....##.# ###.###.## ########## 8 9 4 3
output:
10
result:
ok single line: '10'
Test #5:
score: 0
Accepted
time: 5ms
memory: 35680kb
input:
10 10 ########## #.#.#....# ##..#....# #...####.# #.##.#..## ##..##..## #..##..#.# #.#....#.# #....#...# ########## 4 9 2 2
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 35704kb
input:
10 10 ########## #........# #........# #........# #........# #........# #........# #........# #........# ########## 4 4 7 7
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 3ms
memory: 36212kb
input:
10 6 ###### #....# #....# #....# #....# #....# #....# #....# #....# ###### 3 3 8 4
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 3ms
memory: 35688kb
input:
10 9 ######### ##.....## #.......# #.......# #....#..# #.....#.# #..#..#.# #.#####.# #.#....## ######### 5 4 9 5
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 9ms
memory: 35716kb
input:
10 10 ########## #..#.....# #...##.#.# #....#...# #...#.#.## #......#.# #.......## #...#..#.# #......#.# ########## 2 3 2 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 9ms
memory: 35672kb
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: 42064kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
69
result:
ok single line: '69'
Test #12:
score: 0
Accepted
time: 16ms
memory: 41760kb
input:
200 200 ######################################################################################################################################################################################################## #....................................................................................#........
output:
27
result:
ok single line: '27'
Test #13:
score: 0
Accepted
time: 18ms
memory: 41672kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................#...............
output:
12
result:
ok single line: '12'
Test #14:
score: 0
Accepted
time: 8ms
memory: 39920kb
input:
200 200 ######################################################################################################################################################################################################## #......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......
output:
42
result:
ok single line: '42'
Test #15:
score: 0
Accepted
time: 7ms
memory: 37520kb
input:
200 200 ######################################################################################################################################################################################################## #.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 19ms
memory: 41904kb
input:
200 200 ######################################################################################################################################################################################################## #...#.............##.#................................................#.#.....................
output:
28
result:
ok single line: '28'
Test #17:
score: 0
Accepted
time: 11ms
memory: 40160kb
input:
200 200 ######################################################################################################################################################################################################## #.........#.......#............#...........#...#.............#.......................#........
output:
390
result:
ok single line: '390'
Test #18:
score: 0
Accepted
time: 16ms
memory: 39436kb
input:
200 200 ######################################################################################################################################################################################################## #.....#.......................................#....................#...#........#....#........
output:
501
result:
ok single line: '501'
Test #19:
score: 0
Accepted
time: 16ms
memory: 40360kb
input:
200 200 ######################################################################################################################################################################################################## #.........##.....#..........#.#..............##..#................#..................#........
output:
82
result:
ok single line: '82'
Test #20:
score: 0
Accepted
time: 17ms
memory: 41364kb
input:
190 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
110
result:
ok single line: '110'
Test #21:
score: 0
Accepted
time: 16ms
memory: 38200kb
input:
200 200 ######################################################################################################################################################################################################## #..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....
output:
25350
result:
ok single line: '25350'
Test #22:
score: 0
Accepted
time: 3ms
memory: 36944kb
input:
200 195 ################################################################################################################################################################################################### #..................................................................................................
output:
12813
result:
ok single line: '12813'
Test #23:
score: 0
Accepted
time: 12ms
memory: 39604kb
input:
200 200 ######################################################################################################################################################################################################## #....#....................#..#......#............#................#........#..................
output:
134
result:
ok single line: '134'
Test #24:
score: 0
Accepted
time: 21ms
memory: 41260kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
191
result:
ok single line: '191'
Test #25:
score: 0
Accepted
time: 12ms
memory: 38968kb
input:
200 200 ######################################################################################################################################################################################################## #....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....
output:
330
result:
ok single line: '330'
Test #26:
score: 0
Accepted
time: 10ms
memory: 38880kb
input:
200 200 ######################################################################################################################################################################################################## #.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........
output:
408
result:
ok single line: '408'
Subtask #3:
score: 22
Accepted
Test #27:
score: 22
Accepted
time: 609ms
memory: 188612kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
126
result:
ok single line: '126'
Test #28:
score: 0
Accepted
time: 650ms
memory: 188636kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
81
result:
ok single line: '81'
Test #29:
score: 0
Accepted
time: 697ms
memory: 188056kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
9
result:
ok single line: '9'
Test #30:
score: 0
Accepted
time: 547ms
memory: 171764kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
46
result:
ok single line: '46'
Test #31:
score: 0
Accepted
time: 176ms
memory: 81192kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
-1
result:
ok single line: '-1'
Test #32:
score: 0
Accepted
time: 555ms
memory: 188512kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1994
result:
ok single line: '1994'
Test #33:
score: 0
Accepted
time: 118ms
memory: 65652kb
input:
500 500 ####################################################################################################################################################################################################################################################################################################...
output:
433
result:
ok single line: '433'
Test #34:
score: 0
Accepted
time: 406ms
memory: 159476kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
675
result:
ok single line: '675'
Test #35:
score: 0
Accepted
time: 549ms
memory: 183760kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
506
result:
ok single line: '506'
Test #36:
score: 0
Accepted
time: 471ms
memory: 162456kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
319
result:
ok single line: '319'
Test #37:
score: 0
Accepted
time: 287ms
memory: 126488kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
1141
result:
ok single line: '1141'
Test #38:
score: 0
Accepted
time: 639ms
memory: 186900kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
99
result:
ok single line: '99'
Test #39:
score: 0
Accepted
time: 273ms
memory: 94408kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
660018
result:
ok single line: '660018'
Test #40:
score: 0
Accepted
time: 70ms
memory: 62800kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
332551
result:
ok single line: '332551'
Extra Test:
score: 0
Extra Test Passed