| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 72385 |
2018-08-26T07:36:00 Z |
The quick brown fox jumps over the lazy dog(#2200, khsoo01) |
Aquatic Labyrinth (FXCUP3_aqua) |
C++17 |
|
985 ms |
72672 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 905, inf = 1e18;
const ll dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, 1, -1};
const ll LL = 4, RR = 3, DD = 1, UU = 2;
char ipt[N][N];
ll n, dis[N][N][5], ver[N][N], hor[N][N];
ll l[N][N], r[N][N], d[N][N], u[N][N];
pll s, e;
priority_queue<pair<ll, pair<pll, ll> > > pq;
bool valid (ll X, ll Y) {
return (1 <= X && X <= n && 1 <= Y && Y <= n && ipt[X][Y] != 'W');
}
ll sq (ll X) {
return X*X;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++) {
scanf("%s",ipt[i]+1);
for(ll j=1;j<=n;j++) {
if(ipt[i][j] == 'M') {
s = {i, j};
ipt[i][j] = '.';
}
if(ipt[i][j] == 'H') {
e = {i, j};
ipt[i][j] = '.';
}
ver[i][j] = ver[i-1][j] + (ipt[i][j] == 'W');
hor[i][j] = hor[i][j-1] + (ipt[i][j] == 'W');
for(ll k=0;k<5;k++) {
dis[i][j][k] = inf;
}
}
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=n;j++) {
if(ipt[i][j] == 'W' && ipt[i][j-1] != 'W') l[i][j] = j-1;
else l[i][j] = l[i][j-1];
if(ipt[i][j] == 'W' && ipt[i-1][j] != 'W') u[i][j] = i-1;
else u[i][j] = u[i-1][j];
}
}
for(ll i=n;i>=1;i--) {
for(ll j=n;j>=1;j--) {
if(ipt[i][j] == 'W' && ipt[i][j+1] != 'W') r[i][j] = j+1;
else r[i][j] = r[i][j+1];
if(ipt[i][j] == 'W' && ipt[i+1][j] != 'W') d[i][j] = i+1;
else d[i][j] = d[i+1][j];
}
}
dis[s.X][s.Y][0] = 0;
pq.push({0, {{s.X, s.Y}, 0}});
while(!pq.empty()) {
auto C = pq.top(); pq.pop();
ll V = -C.X, X = C.Y.X.X, Y = C.Y.X.Y, D = C.Y.Y;
if(dis[X][Y][D] != V) continue;
ll NX, NY, ND, NV;
NX = X, NY = l[X][Y], ND = LL, NV = V + sq(hor[NX][NY] - hor[X][Y]);
if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
dis[NX][NY][ND] = NV;
pq.push({-NV, {{NX, NY}, ND}});
}
NX = X, NY = r[X][Y], ND = RR, NV = V + sq(hor[NX][NY] - hor[X][Y]);
if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
dis[NX][NY][ND] = NV;
pq.push({-NV, {{NX, NY}, ND}});
}
NX = d[X][Y], NY = Y, ND = DD, NV = V + sq(ver[NX][NY] - ver[X][Y]);
if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
dis[NX][NY][ND] = NV;
pq.push({-NV, {{NX, NY}, ND}});
}
NX = u[X][Y], NY = Y, ND = UU, NV = V + sq(ver[NX][NY] - ver[X][Y]);
if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
dis[NX][NY][ND] = NV;
pq.push({-NV, {{NX, NY}, ND}});
}
NX = X+dx[D], NY = Y+dy[D], ND = D, NV = V;
if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
dis[NX][NY][ND] = NV;
pq.push({-NV, {{NX, NY}, ND}});
}
}
ll ans = inf;
for(ll i=0;i<5;i++) {
ans = min(ans, dis[e.X][e.Y][i]);
}
printf("%lld\n",ans == inf ? -1 : ans);
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
aqua.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",ipt[i]+1);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
996 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1188 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2632 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3784 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4132 KB |
Output is correct |
| 7 |
Correct |
11 ms |
4456 KB |
Output is correct |
| 8 |
Correct |
12 ms |
4456 KB |
Output is correct |
| 9 |
Correct |
8 ms |
4456 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
996 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1188 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2632 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3784 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4132 KB |
Output is correct |
| 7 |
Correct |
11 ms |
4456 KB |
Output is correct |
| 8 |
Correct |
12 ms |
4456 KB |
Output is correct |
| 9 |
Correct |
8 ms |
4456 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4456 KB |
Output is correct |
| 11 |
Correct |
113 ms |
20176 KB |
Output is correct |
| 12 |
Correct |
133 ms |
42508 KB |
Output is correct |
| 13 |
Correct |
624 ms |
59752 KB |
Output is correct |
| 14 |
Correct |
378 ms |
63892 KB |
Output is correct |
| 15 |
Correct |
56 ms |
64776 KB |
Output is correct |
| 16 |
Correct |
985 ms |
72672 KB |
Output is correct |
| 17 |
Correct |
965 ms |
72672 KB |
Output is correct |
| 18 |
Correct |
333 ms |
72672 KB |
Output is correct |
| 19 |
Correct |
512 ms |
72672 KB |
Output is correct |
| 20 |
Correct |
61 ms |
72672 KB |
Output is correct |
