| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259664 |
2020-08-08T07:28:11 Z |
arnold518 |
None (JOI16_skating) |
C++14 |
|
1331 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 ll INF = 1e18;
int N, M;
char S[MAXN+10][MAXN+10];
int L[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10], U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10];
pii P, Q;
struct Queue
{
int y, x, d; ll w;
bool operator < (const Queue &p) const { return w>p.w; }
};
priority_queue<Queue> PQ;
ll dist[MAXN+10][MAXN+10][2];
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=N; i++) scanf("%s", S[i]+1);
scanf("%d%d%d%d", &P.first, &P.second, &Q.first, &Q.second);
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
{
if(S[i][j]=='#') U[i][j]=i;
else U[i][j]=U[i-1][j];
if(S[i][j]=='#') L[i][j]=j;
else L[i][j]=L[i][j-1];
}
for(int i=N; i>=1; i--) for(int j=M; j>=1; j--)
{
if(S[i][j]=='#') D[i][j]=i;
else D[i][j]=D[i+1][j];
if(S[i][j]=='#') R[i][j]=j;
else R[i][j]=R[i][j+1];
}
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
{
L[i][j]++; R[i][j]--;
U[i][j]++; D[i][j]--;
}
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) for(int k=0; k<2; k++) dist[i][j][k]=INF;
PQ.push({P.first, P.second, 0});
PQ.push({P.first, P.second, 1});
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(dist[now.y][now.x][now.d]<=now.w) continue;
dist[now.y][now.x][now.d]=now.w;
if(now.d==0)
{
for(int i=L[now.y][now.x]; i<now.x; i++) PQ.push({now.y, i, 1, now.w+min(1+(i-L[now.y][now.x])*2, (now.x-i)*2)});
for(int i=now.x+1; i<=R[now.y][now.x]; i++) PQ.push({now.y, i, 1, now.w+min(1+(R[now.y][now.x]-i)*2, (i-now.x)*2)});
}
else
{
for(int i=U[now.y][now.x]; i<now.y; i++) PQ.push({i, now.x, 0, now.w+min(1+(i-U[now.y][now.x])*2, (now.y-i)*2)});
for(int i=now.y+1; i<=D[now.y][now.x]; i++) PQ.push({i, now.x, 0, now.w+min(1+(D[now.y][now.x]-i)*2, (i-now.y)*2)});
}
}
ll ans=min(dist[Q.first][Q.second][0], dist[Q.first][Q.second][1]);
if(ans==INF) ans=-1;
printf("%lld\n", ans);
}
Compilation message
skating.cpp: In function 'int main()':
skating.cpp:27: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:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=N; i++) scanf("%s", S[i]+1);
~~~~~^~~~~~~~~~~~~~
skating.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &P.first, &P.second, &Q.first, &Q.second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
512 KB |
Output is correct |
| 4 |
Correct |
0 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
640 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
512 KB |
Output is correct |
| 4 |
Correct |
0 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
640 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Runtime error |
1331 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 |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
512 KB |
Output is correct |
| 4 |
Correct |
0 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
640 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Runtime error |
1331 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
