QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361224 | #411. Dangerous Skating | Master | 0 | 5ms | 21880kb | C++14 | 3.6kb | 2024-03-22 23:29:46 | 2024-03-22 23:29:48 |
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));
deque<int> q;
q.push_back(F(sx,sy));
d[F(sx,sy)] = 0;
while (q.size()){
int x = q.front(); q.pop_front();
// 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;
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 14784kb
input:
10 10 ########## #....#.### #.......## #........# #.......## ##.......# #.......## #.....#.## #.....#..# ########## 4 7 8 5
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 65
Accepted
time: 5ms
memory: 20652kb
input:
200 200 ######################################################################################################################################################################################################## #.............................................................................................
output:
69
result:
ok single line: '69'
Test #12:
score: -65
Wrong Answer
time: 3ms
memory: 21880kb
input:
200 200 ######################################################################################################################################################################################################## #....................................................................................#........
output:
28
result:
wrong answer 1st lines differ - expected: '27', found: '28'
Subtask #3:
score: 0
Runtime Error
Test #27:
score: 0
Runtime Error
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...