QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361231 | #411. Dangerous Skating | Master | 78 | 9ms | 25108kb | C++14 | 3.7kb | 2024-03-22 23:47:25 | 2024-03-22 23:47:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n,m;
int sx,sy,tx,ty;
int head[N * N], ver[(N * N) << 1], nxt[(N * N) << 1], edge[(N * N) << 1], tot;
char a[N][N];
void add(int x,int y,int z){
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
int Next[N][N][4];
// shang: 0, xia: 1, zuo: 2, you: 3
int F(int x,int y){
return (x - 1) * m + y;
}
int d[N * N];
bool v[N * N];
void bfs(){
memset(d,0x3f,sizeof(d));
priority_queue<pair<int,int>> q;
q.push({0,F(sx,sy)});
d[F(sx,sy)] = 0;
while (q.size()){
int x = q.top().second; q.pop();
// cout << x << ' ' << d[x] << '\n';
if (v[x]) continue;
v[x] = 1;
for (int i = head[x];i;i = nxt[i]){
int y = ver[i], z = edge[i];
// cout << "edge:" << x << ' ' << y << ' ' << z << '\n';
if (d[y] > d[x] + z){
d[y] = d[x] + z;
q.push({-d[y],y});
// if (z == 1)
// q.push_front(y);
// else
// q.push_back(y);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++)
scanf("%s", a[i] + 1);
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
for (int j = 1;j <= m;j++){
int pre = -1;
for (int i = 1;i <= n;i++){
if (a[i][j] == '.'){
Next[i][j][0] = pre;
if (pre == -1)
pre = F(i,j);
}
else
pre = -1;
}
}
for (int j = 1;j <= m;j++){
int pre = -1;
for (int i = n;i >= 1;i--){
if (a[i][j] == '.'){
Next[i][j][1] = pre;
if (pre == -1)
pre = F(i,j);
}
else
pre = -1;
}
}
for (int i = 1;i <= n;i++){
int pre = -1;
for (int j = 1;j <= m;j++){
if (a[i][j] == '.'){
Next[i][j][2] = pre;
if (pre == -1)
pre = F(i,j);
}
else
pre = -1;
}
}
for (int i = 1;i <= n;i++){
int pre = -1;
for (int j = m;j >= 1;j--){
if (a[i][j] == '.'){
Next[i][j][3] = pre;
if (pre == -1)
pre = F(i,j);
}
else
pre = -1;
}
}
// for (int i = 1;i <= n;i++){
// for (int j = 1;j <= m;j++){
// cout << i << ' ' << j << ' ' << Next[i][j][3] << '\n';
// }
// }
// return 0;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
if (a[i][j] == '.'){
if (a[i + 1][j] == '.' && F(i + 1,j) != Next[i][j][1])
add(F(i,j),F(i + 1,j),2);
if (a[i][j + 1] == '.' && F(i,j + 1) != Next[i][j][3])
add(F(i,j),F(i,j + 1),2);
if (a[i - 1][j] == '.' && F(i - 1,j) != Next[i][j][0])
add(F(i,j),F(i - 1,j),2);
if (a[i][j - 1] == '.' && F(i,j - 1) != Next[i][j][2])
add(F(i,j),F(i,j - 1),2);
}
}
}
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
for (int k = 0;k < 4;k++)
if (Next[i][j][k] != -1 && a[i][j] == '.')
add(F(i,j),Next[i][j][k],1)/*, cout << k << ' ' << F(i,j) << ' ' << Next[i][j][k] << '\n'*/;
// return 0;
bfs();
if (!v[F(tx,ty)]) d[F(tx,ty)] = -1;
printf("%d",d[F(tx,ty)]);
return 0;
}
详细
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 0ms
memory: 16088kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 16140kb
input:
10 10 ########## #.....#.## #....#...# #..#....## #........# #.#......# #...##.#.# #........# #..#.....# ########## 9 9 9 8
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 16072kb
input:
10 10 ########## #..#.....# #....#.#.# ##..#.##.# ##......## ##.#...#.# #..#.##..# #..###...# ##...#..## ########## 4 9 5 6
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 2ms
memory: 16072kb
input:
10 10 ########## ##.####### ##.#.##.## ##.###.### #.....#.## #####..### ######...# ##....##.# ###.###.## ########## 8 9 4 3
output:
10
result:
ok single line: '10'
Test #5:
score: 0
Accepted
time: 2ms
memory: 16076kb
input:
10 10 ########## #.#.#....# ##..#....# #...####.# #.##.#..## ##..##..## #..##..#.# #.#....#.# #....#...# ########## 4 9 2 2
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 16072kb
input:
10 10 ########## #........# #........# #........# #........# #........# #........# #........# #........# ########## 4 4 7 7
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 0ms
memory: 14436kb
input:
10 6 ###### #....# #....# #....# #....# #....# #....# #....# #....# ###### 3 3 8 4
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 0ms
memory: 14936kb
input:
10 9 ######### ##.....## #.......# #.......# #....#..# #.....#.# #..#..#.# #.#####.# #.#....## ######### 5 4 9 5
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 2ms
memory: 14932kb
input:
10 10 ########## #..#.....# #...##.#.# #....#...# #...#.#.## #......#.# #.......## #...#..#.# #......#.# ########## 2 3 2 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 2ms
memory: 16148kb
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: 9ms
memory: 19596kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
69
result:
ok single line: '69'
Test #12:
score: 0
Accepted
time: 5ms
memory: 25108kb
input:
200 200 ######################################################################################################################################################################################################## #....................................................................................#........
output:
27
result:
ok single line: '27'
Test #13:
score: 0
Accepted
time: 6ms
memory: 19612kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................#...............
output:
12
result:
ok single line: '12'
Test #14:
score: 0
Accepted
time: 4ms
memory: 21392kb
input:
200 200 ######################################################################################################################################################################################################## #......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......
output:
42
result:
ok single line: '42'
Test #15:
score: 0
Accepted
time: 5ms
memory: 18776kb
input:
200 200 ######################################################################################################################################################################################################## #.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 4ms
memory: 19748kb
input:
200 200 ######################################################################################################################################################################################################## #...#.............##.#................................................#.#.....................
output:
28
result:
ok single line: '28'
Test #17:
score: 0
Accepted
time: 4ms
memory: 23508kb
input:
200 200 ######################################################################################################################################################################################################## #.........#.......#............#...........#...#.............#.......................#........
output:
390
result:
ok single line: '390'
Test #18:
score: 0
Accepted
time: 0ms
memory: 19288kb
input:
200 200 ######################################################################################################################################################################################################## #.....#.......................................#....................#...#........#....#........
output:
501
result:
ok single line: '501'
Test #19:
score: 0
Accepted
time: 9ms
memory: 21448kb
input:
200 200 ######################################################################################################################################################################################################## #.........##.....#..........#.#..............##..#................#..................#........
output:
82
result:
ok single line: '82'
Test #20:
score: 0
Accepted
time: 0ms
memory: 21456kb
input:
190 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
110
result:
ok single line: '110'
Test #21:
score: 0
Accepted
time: 0ms
memory: 18784kb
input:
200 200 ######################################################################################################################################################################################################## #..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....
output:
25350
result:
ok single line: '25350'
Test #22:
score: 0
Accepted
time: 0ms
memory: 20868kb
input:
200 195 ################################################################################################################################################################################################### #..................................................................................................
output:
12813
result:
ok single line: '12813'
Test #23:
score: 0
Accepted
time: 2ms
memory: 22736kb
input:
200 200 ######################################################################################################################################################################################################## #....#....................#..#......#............#................#........#..................
output:
134
result:
ok single line: '134'
Test #24:
score: 0
Accepted
time: 4ms
memory: 24928kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
191
result:
ok single line: '191'
Test #25:
score: 0
Accepted
time: 3ms
memory: 19144kb
input:
200 200 ######################################################################################################################################################################################################## #....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....
output:
330
result:
ok single line: '330'
Test #26:
score: 0
Accepted
time: 7ms
memory: 20780kb
input:
200 200 ######################################################################################################################################################################################################## #.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........
output:
408
result:
ok single line: '408'
Subtask #3:
score: 0
Runtime Error
Test #27:
score: 0
Runtime Error
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...