#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1000;
const int INF = 987654321;
struct Queue
{
short y, x; bool p; int d;
bool operator < (const Queue &p) const { return d>p.d; }
};
int N, M, SY, SX, EY, EX;
char S[MAXN+10][MAXN+10];
int dist[MAXN+10][MAXN+10][2];
int U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10], L[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10];
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i=1; i<=N; i++) scanf("%s", S[i]+1);
scanf("%d%d%d%d", &SY, &SX, &EY, &EX);
for(i=1; i<=N; i++) for(j=1; j<=M; j++)
{
if(S[i][j]=='#') U[i][j]=i, L[i][j]=j;
else U[i][j]=U[i-1][j], L[i][j]=L[i][j-1];
}
for(i=N; i>=1; i--) for(j=M; j>=1; j--)
{
if(S[i][j]=='#') D[i][j]=i, R[i][j]=j;
else D[i][j]=D[i+1][j], R[i][j]=R[i][j+1];
}
for(i=1; i<=N; i++) for(j=1; j<=M; j++) dist[i][j][0]=dist[i][j][1]=INF;
priority_queue<Queue> PQ;
PQ.push({SY, SX, 0, 0});
PQ.push({SY, SX, 1, 0});
while(!PQ.empty())
{
Queue T=PQ.top(); PQ.pop();
if(dist[T.y][T.x][T.p]<=T.d) continue;
dist[T.y][T.x][T.p]=T.d;
if(T.p==0)
{
int l, r, k;
l=L[T.y][T.x]+1, r=T.x-1, k=0;
for(i=1; l<=r; i++)
{
if(k==0)
{
if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
k=1; l++;
}
else
{
if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
r--; k=0;
}
}
l=T.x+1, r=R[T.y][T.x]-1, k=0;
for(i=1; l<=r; i++)
{
if(k==1)
{
if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
l++; k=0;
}
else
{
if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
r--; k=1;
}
}
if(dist[T.y][T.x][1]>T.d) PQ.push({T.y, T.x, 1, T.d});
}
else
{
int l, r, k;
l=U[T.y][T.x]+1, r=T.y-1, k=0;
for(i=1; l<=r; i++)
{
if(k==0)
{
if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
l++; k=1;
}
else
{
if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
r--; k=0;
}
}
l=T.y+1, r=D[T.y][T.x]-1, k=0;
for(i=1; l<=r; i++)
{
if(k==1)
{
if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
l++; k=0;
}
else
{
if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
r--; k=1;
}
}
if(dist[T.y][T.x][0]>T.d) PQ.push({T.y, T.x, 0, T.d});
}
}
int ans=min(dist[EY][EX][1], dist[EY][EX][0]);
if(ans==INF) printf("-1\n");
else printf("%d\n", ans);
}
Compilation message
skating.cpp: In function 'int main()':
skating.cpp:44:24: warning: narrowing conversion of 'SY' from 'int' to 'short int' inside { } [-Wnarrowing]
PQ.push({SY, SX, 0, 0});
^
skating.cpp:44:24: warning: narrowing conversion of 'SX' from 'int' to 'short int' inside { } [-Wnarrowing]
skating.cpp:45:24: warning: narrowing conversion of 'SY' from 'int' to 'short int' inside { } [-Wnarrowing]
PQ.push({SY, SX, 1, 0});
^
skating.cpp:45:24: warning: narrowing conversion of 'SX' from 'int' to 'short int' inside { } [-Wnarrowing]
skating.cpp:60:58: warning: narrowing conversion of 'l' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
^
skating.cpp:65:58: warning: narrowing conversion of 'r' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
^
skating.cpp:74:58: warning: narrowing conversion of 'l' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
^
skating.cpp:79:58: warning: narrowing conversion of 'r' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
^
skating.cpp:93:58: warning: narrowing conversion of 'l' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
^
skating.cpp:98:58: warning: narrowing conversion of 'r' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
^
skating.cpp:107:58: warning: narrowing conversion of 'l' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
^
skating.cpp:112:58: warning: narrowing conversion of 'r' from 'int' to 'short int' inside { } [-Wnarrowing]
if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
^
skating.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
skating.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%s", S[i]+1);
~~~~~^~~~~~~~~~~~~~
skating.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &SY, &SX, &EY, &EX);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
2234 ms |
103416 KB |
Output is correct |
12 |
Correct |
1654 ms |
103420 KB |
Output is correct |
13 |
Correct |
571 ms |
29516 KB |
Output is correct |
14 |
Correct |
37 ms |
5304 KB |
Output is correct |
15 |
Correct |
8 ms |
4728 KB |
Output is correct |
16 |
Correct |
283 ms |
17240 KB |
Output is correct |
17 |
Correct |
45 ms |
5112 KB |
Output is correct |
18 |
Correct |
26 ms |
4856 KB |
Output is correct |
19 |
Correct |
66 ms |
6512 KB |
Output is correct |
20 |
Correct |
2180 ms |
53932 KB |
Output is correct |
21 |
Correct |
13 ms |
5112 KB |
Output is correct |
22 |
Correct |
113 ms |
5112 KB |
Output is correct |
23 |
Correct |
28 ms |
4984 KB |
Output is correct |
24 |
Correct |
260 ms |
11108 KB |
Output is correct |
25 |
Correct |
21 ms |
4856 KB |
Output is correct |
26 |
Correct |
22 ms |
4856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
2234 ms |
103416 KB |
Output is correct |
12 |
Correct |
1654 ms |
103420 KB |
Output is correct |
13 |
Correct |
571 ms |
29516 KB |
Output is correct |
14 |
Correct |
37 ms |
5304 KB |
Output is correct |
15 |
Correct |
8 ms |
4728 KB |
Output is correct |
16 |
Correct |
283 ms |
17240 KB |
Output is correct |
17 |
Correct |
45 ms |
5112 KB |
Output is correct |
18 |
Correct |
26 ms |
4856 KB |
Output is correct |
19 |
Correct |
66 ms |
6512 KB |
Output is correct |
20 |
Correct |
2180 ms |
53932 KB |
Output is correct |
21 |
Correct |
13 ms |
5112 KB |
Output is correct |
22 |
Correct |
113 ms |
5112 KB |
Output is correct |
23 |
Correct |
28 ms |
4984 KB |
Output is correct |
24 |
Correct |
260 ms |
11108 KB |
Output is correct |
25 |
Correct |
21 ms |
4856 KB |
Output is correct |
26 |
Correct |
22 ms |
4856 KB |
Output is correct |
27 |
Runtime error |
693 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |