#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 900LL*900*900*900+9;
int dx[4] = {-1,0,0,1}, dy[4] = {0,1,-1,0};
inline int sq(int x) {
return x*x;
}
char fl[909][909];
long long dist[909][909];
int g[909][909][4][3];
int n;
int main() {
scanf("%d",&n);
int sy, sx, ey, ex;
for(int i=0;i<n;i++) {
scanf("%s",fl[i]);
for(int j=0;j<n;j++) {
if(fl[i][j] == 'M') {
sy = i;
sx = j;
fl[i][j] = '.';
} else if(fl[i][j] == 'H') {
ey = i;
ex = j;
fl[i][j] = '.';
}
}
}
// UP DOWN
for(int j=0;j<n;j++) {
int pl=0, pr=-1,cl=0;
bool bl = true;
for(int i=0;i<n;i++) {
if(bl) {
if(fl[i][j] == 'W') continue;
bl = false;
cl = i;
} else {
if(fl[i][j] == '.') continue;
int cost = sq(cl-pr-1);
int cr = i-1;
for(int k=pl;k<=pr;k++) {
g[k][j][1][0] = cl;
g[k][j][1][1] = cr;
g[k][j][1][2] = cost;
}
for(int k=cl;k<=cr;k++) {
g[k][j][2][0] = pl;
g[k][j][2][1] = pr;
g[k][j][2][2] = cost;
}
pl = cl;
pr = cr;
bl = true;
}
}
if(!bl) {
int cost = sq(cl-pr-1);
int cr = n-1;
for(int k=pl;k<=pr;k++) {
g[k][j][1][0] = cl;
g[k][j][1][1] = cr;
g[k][j][1][2] = cost;
}
for(int k=cl;k<=cr;k++) {
g[k][j][2][0] = pl;
g[k][j][2][1] = pr;
g[k][j][2][2] = cost;
}
}
}
// LEFT RIGHT
for(int i=0;i<n;i++) {
int pl=0, pr=-1,cl=0;
bool bl = true;
for(int j=0;j<n;j++) {
if(bl) {
if(fl[i][j] == 'W') continue;
bl = false;
cl = j;
} else {
if(fl[i][j] == '.') continue;
int cost = sq(cl-pr-1);
int cr = j-1;
for(int k=pl;k<=pr;k++) {
g[i][k][3][0] = cl;
g[i][k][3][1] = cr;
g[i][k][3][2] = cost;
}
for(int k=cl;k<=cr;k++) {
g[i][k][0][0] = pl;
g[i][k][0][1] = pr;
g[i][k][0][2] = cost;
}
pl = cl;
pr = cr;
bl = true;
}
}
if(!bl) {
int cost = sq(cl-pr-1);
int cr = n-1;
for(int k=pl;k<=pr;k++) {
g[i][k][3][0] = cl;
g[i][k][3][1] = cr;
g[i][k][3][2] = cost;
}
for(int k=cl;k<=cr;k++) {
g[i][k][0][0] = pl;
g[i][k][0][1] = pr;
g[i][k][0][2] = cost;
}
}
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j] = inf;
dist[sy][sx] = 0;
priority_queue<tuple<ll, int, int>> pq;
pq.emplace(0,sy,sx);
while(!pq.empty()) {
// auto [w,y,x] = pq.top();
ll w;
int y,x;
tie(w,y,x) = pq.top();
if(y == ey && x == ex) break;
pq.pop();
w = -w;
if(w != dist[y][x]) continue;
for(int k=0;k<4;k++) {
if(k == 0 || k == 3) {
for(int xx = g[y][x][k][0]; xx<=g[y][x][k][1]; xx++) {
ll ww = w + g[y][x][k][2];
if(dist[y][xx] <= ww) continue;
dist[y][xx] = ww;
pq.emplace(-ww,y,xx);
}
} else {
for(int yy = g[y][x][k][0]; yy<=g[y][x][k][1]; yy++) {
ll ww = w + g[y][x][k][2];
if(dist[yy][x] <= ww) continue;
dist[yy][x] = ww;
pq.emplace(-ww,yy,x);
}
}
}
}
if(dist[ey][ex] == inf) puts("-1");
else printf("%lld\n",dist[ey][ex]);
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",fl[i]);
~~~~~^~~~~~~~~~~~
aqua.cpp:133:5: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(y == ey && x == ex) break;
^~
aqua.cpp:133:16: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(y == ey && x == ex) break;
~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
