#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pli pair<long long,int>
using namespace std;
int n, Num[910][910], NX[910][910], NY[910][910], BX[910], EX[910], BY[910], EY[910];
int L[3010000];
long long D[3010000];
char p[910][910];
priority_queue<pli>PQ;
vector<int>E[3010000], LL[3010000];
void Add_Edge(int a, int b, int d) {
E[a].push_back(b);
LL[a].push_back(d*d);
}
void Put(int a, long long d) {
if (D[a] <= d)return;
D[a] = d;
PQ.push({ -d,a });
}
int main() {
//freopen("input.txt", "r", stdin);
int i, j, sx, sy, cnt = 0, ex, ey;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%s", p[i]+1);
for (j = 1; j <= n; j++){
if (p[i][j] == 'M') {
sx = i, sy = j;
p[i][j] = '.';
}
if (p[i][j] == 'H') {
ex = i, ey = j;
p[i][j] = '.';
}
if (p[i][j] == '.') {
cnt++;
Num[i][j] = cnt;
}
}
}
for (i = 1; i <= n; i++) {
BX[i] = cnt + 1;
int c = 0, cp = 0;
for (j = 1; j <= n; j++) {
if (p[i][j] == '.') {
if (p[i][j - 1] != '.')cnt++;
if (c) {
cp = c;
c = 0;
L[cnt] = cp;
}
NX[i][j] = cnt;
}
if (p[i][j] == 'W') {
c++;
}
}
EX[i] = cnt;
}
for (i = 1; i <= n; i++) {
BY[i] = cnt + 1;
int c = 0, cp = 0;
for (j = 1; j <= n; j++) {
if (p[j][i] == '.') {
if (p[j - 1][i] != '.')cnt++;
if (c) {
cp = c;
c = 0;
L[cnt] = cp;
}
NY[j][i] = cnt;
}
if (p[j][i] == 'W') {
c++;
}
}
EY[i] = cnt;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
Add_Edge(NX[i][j], Num[i][j], 0);
Add_Edge(NY[i][j], Num[i][j], 0);
if (NX[i][j] != BX[i]) {
Add_Edge(Num[i][j], NX[i][j] - 1, L[NX[i][j]]);
}
if (NX[i][j] != EX[i]) {
Add_Edge(Num[i][j], NX[i][j] + 1, L[NX[i][j] + 1]);
}
if (NY[i][j] != BY[j]) {
Add_Edge(Num[i][j], NY[i][j] - 1, L[NY[i][j]]);
}
if (NY[i][j] != EY[j]) {
Add_Edge(Num[i][j], NY[i][j] + 1, L[NY[i][j] + 1]);
}
}
}
for (i = 1; i <= cnt; i++)D[i] = 1e18;
Put(Num[sx][sy], 0);
while (!PQ.empty()) {
pli tp = PQ.top();
PQ.pop();
int x = tp.second;
if (D[x] != -tp.first)continue;
for (i = 0; i < E[x].size(); i++) {
Put(E[x][i], D[x] + LL[x][i]);
}
}
long long res = D[Num[ex][ey]];
if (res > 8e16)res = -1;
printf("%lld\n", res);
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:106:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < E[x].size(); i++) {
~~^~~~~~~~~~~~~
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:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", p[i]+1);
~~~~~^~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
Put(Num[sx][sy], 0);
~~~^~~~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:110:30: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
long long res = D[Num[ex][ey]];
~~~~~~~~~~^
aqua.cpp:110:30: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
127 ms |
141688 KB |
Output is correct |
| 2 |
Correct |
128 ms |
142056 KB |
Output is correct |
| 3 |
Correct |
127 ms |
142316 KB |
Output is correct |
| 4 |
Correct |
126 ms |
142996 KB |
Output is correct |
| 5 |
Correct |
135 ms |
143272 KB |
Output is correct |
| 6 |
Correct |
143 ms |
143824 KB |
Output is correct |
| 7 |
Correct |
148 ms |
144224 KB |
Output is correct |
| 8 |
Correct |
154 ms |
144224 KB |
Output is correct |
| 9 |
Correct |
143 ms |
144616 KB |
Output is correct |
| 10 |
Correct |
124 ms |
144616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
127 ms |
141688 KB |
Output is correct |
| 2 |
Correct |
128 ms |
142056 KB |
Output is correct |
| 3 |
Correct |
127 ms |
142316 KB |
Output is correct |
| 4 |
Correct |
126 ms |
142996 KB |
Output is correct |
| 5 |
Correct |
135 ms |
143272 KB |
Output is correct |
| 6 |
Correct |
143 ms |
143824 KB |
Output is correct |
| 7 |
Correct |
148 ms |
144224 KB |
Output is correct |
| 8 |
Correct |
154 ms |
144224 KB |
Output is correct |
| 9 |
Correct |
143 ms |
144616 KB |
Output is correct |
| 10 |
Correct |
124 ms |
144616 KB |
Output is correct |
| 11 |
Correct |
267 ms |
157096 KB |
Output is correct |
| 12 |
Correct |
530 ms |
195884 KB |
Output is correct |
| 13 |
Correct |
845 ms |
207372 KB |
Output is correct |
| 14 |
Correct |
601 ms |
207372 KB |
Output is correct |
| 15 |
Correct |
202 ms |
207372 KB |
Output is correct |
| 16 |
Correct |
1114 ms |
234872 KB |
Output is correct |
| 17 |
Correct |
1105 ms |
235720 KB |
Output is correct |
| 18 |
Correct |
1255 ms |
265072 KB |
Output is correct |
| 19 |
Correct |
819 ms |
265072 KB |
Output is correct |
| 20 |
Correct |
299 ms |
265072 KB |
Output is correct |
