#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> adj[2000005];
priority_queue<pii, vector<pii>, greater<pii> > pq;
int D[2000005];
char A[909][909];
int N;
int R[909][909];
int C[909][909];
int Rc[909][909];
int Cc[909][909];
vector<pii> G[2000005];
int cvt(int r, int c, int type) {
if(type == 0) return (r * N + c) * 2;
return (c * N + r) * 2 + 1;
}
int main() {
for(int i = 0; i < 2000005; i++) D[i] = 987654321;
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%s", A[i]);
int sx, sy, ex, ey;
for(int i = 0; i < N; i++) {
int num = 0;
int c = 0;
int j = 0; while(A[i][j] == 'W') j++;
for( ; j < N; j++) {
if(A[i][j] == 'W') { c++; if(A[i][j - 1] != 'W') num++; continue; }
if(A[i][j] == 'M') { sx = i, sy = j; }
if(A[i][j] == 'H') { ex = i, ey = j; }
if(j && A[i][j - 1] == 'W') {
if(num > 0) {
adj[cvt(i, num, 0)].push_back(pii(cvt(i, num - 1, 0), c * c));
adj[cvt(i, num - 1, 0)].push_back(pii(cvt(i, num, 0), c * c));
G[cvt(i, num, 0)].push_back(pii(cvt(i, num - 1, 0), c * c));
G[cvt(i, num - 1, 0)].push_back(pii(cvt(i, num, 0), c * c));
Rc[i][num] = c * c;
}
c = 0;
}
R[i][j] = num;
}
}
for(int j = 0; j < N; j++) {
int num = 0;
int c = 0;
int i = 0; while(A[i][j] == 'W') i++;
for(; i < N; i++) {
if(A[i][j] == 'W') { c++; if(A[i - 1][j] != 'W') num++; }
else if(i && A[i - 1][j] == 'W') {
if(num > 0) {
adj[cvt(num, j, 1)].push_back(pii(cvt(num - 1, j, 1), c * c));
adj[cvt(num - 1, j, 1)].push_back(pii(cvt(num, j, 1), c * c));
G[cvt(num, j, 1)].push_back(pii(cvt(num - 1, j, 1), c * c));
G[cvt(num - 1, j, 1)].push_back(pii(cvt(num, j, 1), c * c));
Cc[num][j] = c * c;
}
c = 0;
}
C[i][j] = num;
}
}
/*
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
//printf("%d ", cvt(C[i][j], j, 1));
printf("%d ", Rc[i][j]);
}
puts("");
}
for(int i = 0; i < 20; i++) {
printf("%d: ", i);
for(pii j : adj[i]) printf("(%d %d) ", j); puts("");
}*/
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(A[i][j] == 'W') continue;
int now = cvt(i, R[i][j], 0);
for(pii k : adj[cvt(C[i][j], j, 1)]) {
G[now].push_back(pii(k));
}
}
}
for(int j = 0; j < N; j++) {
for(int i = 0; i < N; i++) {
if(A[i][j] == 'W') continue;
int now = cvt(C[i][j], j, 1);
for(pii k : adj[cvt(i, R[i][j], 0)]) {
G[now].push_back(pii(k));
}
}
}
for(pii i : adj[cvt(sx, R[sx][sy], 0)]) {
pq.push(pii(i.second, i.first));
D[i.first] = i.second;
//printf("st%d %d\n", i);
}
for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
pq.push(pii(i.second, i.first));
D[i.first] = i.second;
//printf("st%d %d\n", i);
}
while(!pq.empty()) {
int nowd = pq.top().first;
int now = pq.top().second;
pq.pop();
if(D[now] < nowd) continue;
for(pii i : G[now]) {
int nxt = i.first;
if(D[nxt] > D[now] + i.second) {
D[nxt] = D[now] + i.second;
pq.push(pii(D[nxt], nxt));
}
}
}
/*
for(int i = 0; i < 20; i++) {
printf("%d: ", i);
for(pii j : adj[i]) printf("(%d %d) ", j); puts("");
}*/
int ans = min(D[cvt(ex, R[ex][ey], 0)], D[cvt(C[ex][ey], ey, 1)]);
printf("%d\n", (ans == 987654321 ? -1 : ans));
return 0;
}
/*
4
M.W.
.W..
.H..
....
6
M..WW.
W.W.H.
.WW...
W..W.W
.W...W
..W.W.
4
...H
W.W.
M..W
WW..
*/
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
aqua.cpp:26:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < N; i++) scanf("%s", A[i]);
~~~~~^~~~~~~~~~~~
aqua.cpp:115:21: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:141:47: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
int ans = min(D[cvt(ex, R[ex][ey], 0)], D[cvt(C[ex][ey], ey, 1)]);
~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:27:18: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
int sx, sy, ex, ey;
^~
aqua.cpp:27:10: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
int sx, sy, ex, ey;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
102136 KB |
Output is correct |
| 2 |
Correct |
90 ms |
102268 KB |
Output is correct |
| 3 |
Correct |
89 ms |
102584 KB |
Output is correct |
| 4 |
Correct |
93 ms |
103140 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103140 KB |
Output is correct |
| 6 |
Correct |
91 ms |
103836 KB |
Output is correct |
| 7 |
Correct |
99 ms |
104168 KB |
Output is correct |
| 8 |
Correct |
93 ms |
104244 KB |
Output is correct |
| 9 |
Correct |
99 ms |
104832 KB |
Output is correct |
| 10 |
Correct |
91 ms |
104832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
102136 KB |
Output is correct |
| 2 |
Correct |
90 ms |
102268 KB |
Output is correct |
| 3 |
Correct |
89 ms |
102584 KB |
Output is correct |
| 4 |
Correct |
93 ms |
103140 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103140 KB |
Output is correct |
| 6 |
Correct |
91 ms |
103836 KB |
Output is correct |
| 7 |
Correct |
99 ms |
104168 KB |
Output is correct |
| 8 |
Correct |
93 ms |
104244 KB |
Output is correct |
| 9 |
Correct |
99 ms |
104832 KB |
Output is correct |
| 10 |
Correct |
91 ms |
104832 KB |
Output is correct |
| 11 |
Correct |
162 ms |
114016 KB |
Output is correct |
| 12 |
Correct |
387 ms |
148508 KB |
Output is correct |
| 13 |
Correct |
483 ms |
149952 KB |
Output is correct |
| 14 |
Correct |
350 ms |
149952 KB |
Output is correct |
| 15 |
Correct |
123 ms |
149952 KB |
Output is correct |
| 16 |
Correct |
707 ms |
168060 KB |
Output is correct |
| 17 |
Correct |
719 ms |
168104 KB |
Output is correct |
| 18 |
Correct |
861 ms |
203088 KB |
Output is correct |
| 19 |
Correct |
495 ms |
203088 KB |
Output is correct |
| 20 |
Correct |
111 ms |
203088 KB |
Output is correct |
