#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];
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));
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));
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] - 1, 0);
if(R[i][j] > 0) {
for(pii k : adj[cvt(C[i][j], j, 1)]) {
adj[now].push_back(pii(k.first, Rc[i][R[i][j]] + k.second));
}
}
now = cvt(i, R[i][j] + 1, 0);
for(pii k : adj[cvt(C[i][j], j, 1)]) {
//printf("%d->%d\n", now, k.first);
//printf("%d %d %d\n", i, j, k.second);
adj[now].push_back(pii(k.first, Rc[i][R[i][j] + 1] + k.second));
}
}
}
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] - 1, j, 1);
if(C[i][j] > 0) {
for(pii k : adj[cvt(i, R[i][j], 0)]) {
adj[now].push_back(pii(k.first, Cc[C[i][j]][j] + k.second));
}
}
now = cvt(C[i][j] + 1, j, 1);
for(pii k : adj[cvt(i, R[i][j], 0)]) {
adj[now].push_back(pii(k.first, Cc[C[i][j] + 1][j] + k.second));
}
}
}
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 : adj[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..
....
*/
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
aqua.cpp:25: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:26:10: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
int sx, sy, ex, ey;
^~
aqua.cpp:150: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:124:21: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:26:18: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
int sx, sy, ex, ey;
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
53 ms |
55160 KB |
Output is correct |
| 2 |
Correct |
51 ms |
55400 KB |
Output is correct |
| 3 |
Correct |
59 ms |
55644 KB |
Output is correct |
| 4 |
Correct |
51 ms |
56568 KB |
Output is correct |
| 5 |
Correct |
54 ms |
56568 KB |
Output is correct |
| 6 |
Correct |
61 ms |
57412 KB |
Output is correct |
| 7 |
Incorrect |
62 ms |
58052 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
53 ms |
55160 KB |
Output is correct |
| 2 |
Correct |
51 ms |
55400 KB |
Output is correct |
| 3 |
Correct |
59 ms |
55644 KB |
Output is correct |
| 4 |
Correct |
51 ms |
56568 KB |
Output is correct |
| 5 |
Correct |
54 ms |
56568 KB |
Output is correct |
| 6 |
Correct |
61 ms |
57412 KB |
Output is correct |
| 7 |
Incorrect |
62 ms |
58052 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
