| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199571 |
2020-02-02T04:52:26 Z |
arnold518 |
None (JOI16_skating) |
C++14 |
|
1371 ms |
262148 KB |
#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
{
int y, x, p, 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) PQ.push({T.y, l++, 1, T.d+i}), k=1;
else PQ.push({T.y, r--, 1, T.d+i}), k=0;
}
l=T.x+1, r=R[T.y][T.x]-1, k=0;
for(i=1; l<=r; i++)
{
if(k==1) PQ.push({T.y, l++, 1, T.d+i}), k=0;
else PQ.push({T.y, r--, 1, T.d+i}), k=1;
}
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) PQ.push({l++, T.x, 0, T.d+i}), k=1;
else PQ.push({r--, T.x, 0, T.d+i}), k=0;
}
l=T.y+1, r=D[T.y][T.x]-1, k=0;
for(i=1; l<=r; i++)
{
if(k==1) PQ.push({l++, T.x, 0, T.d+i}), k=0;
else PQ.push({r--, T.x, 0, T.d+i}), k=1;
}
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: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
632 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
632 KB |
Output is correct |
| 8 |
Correct |
5 ms |
508 KB |
Output is correct |
| 9 |
Correct |
5 ms |
632 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
632 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
632 KB |
Output is correct |
| 8 |
Correct |
5 ms |
508 KB |
Output is correct |
| 9 |
Correct |
5 ms |
632 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| 11 |
Runtime error |
1371 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
632 KB |
Output is correct |
| 6 |
Correct |
5 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
632 KB |
Output is correct |
| 8 |
Correct |
5 ms |
508 KB |
Output is correct |
| 9 |
Correct |
5 ms |
632 KB |
Output is correct |
| 10 |
Correct |
5 ms |
504 KB |
Output is correct |
| 11 |
Runtime error |
1371 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
