#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);
}
/*#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 303000
#define M_ 1010000
#define INF 99999999
using namespace std;
int n;
struct Edge {
int b, e, f;
};
class MaxFlow {
public:
Edge E[M_ * 2];
vector<int>G[N_];
int Level[N_], Q[N_], PV[N_], source, sink, n, flow, EC;
void init(int N, int S, int T) {
n = N, flow = EC = 0;
source = S, sink = T;
for (int i = 0; i <= N; i++)G[i].clear();
}
void Add_Edge(int a, int b, int f) {
G[a].push_back(EC);
G[b].push_back(EC + 1);
E[EC++] = { a,b,f};
E[EC++] = { b,a,0};
}
bool GetLevel() {
int i;
for (i = 1; i <= n; i++)Level[i] = -1;
int head = 0, tail = 0;
Q[++tail] = source, Level[source] = 0;
while (head < tail) {
int x = Q[++head];
for (auto &y : G[x]) {
if (E[y].f && Level[E[y].e] == -1) {
Q[++tail] = E[y].e;
Level[E[y].e] = Level[x] + 1;
}
}
}
return Level[sink] != -1;
}
int BlockFlow(int a, int f) {
if (a == sink)return f;
for (int &i = PV[a]; i >= 0; i--) {
int x = G[a][i];
if (E[x].f && Level[E[x].e] == Level[a] + 1) {
int t = BlockFlow(E[x].e, min(f, E[x].f));
if (t) {
E[x].f -= t;
E[x ^ 1].f += t;
return t;
}
}
}
return 0;
}
void Dinic() {
int t;
while (GetLevel()) {
for (int i = 1; i <= n; i++)PV[i] = G[i].size() - 1;
while (t = BlockFlow(source, INF)) flow += t;
}
}
}G1;
vector<int>E[N_];
int Col[N_];
void DFS(int a, int pp, int col) {
Col[a] = col;
for (auto &x : E[a]) {
if (x == pp)continue;
DFS(x, a, 3 - col);
}
}
int main() {
freopen("input.txt", "r", stdin);
int i, a, b;
scanf("%d", &n);
G1.init(n + 2, n + 1, n + 2);
for (i = 1; i < n; i++) {
scanf("%d%d", &a, &b);
E[a].push_back(b);
E[b].push_back(a);
}
DFS(1, 0, 1);
for (i = 1; i <= n; i++) {
for (auto &x : E[i]) {
if (Col[i] == 1) G1.Add_Edge(i, x, 1);
}
if (Col[i] == 1)G1.Add_Edge(G1.source, i, n - 1 - E[i].size());
else G1.Add_Edge(i, G1.sink, n - 1 - E[i].size());
}
G1.Dinic();
printf("%d\n", G1.flow);
for (i = 1; i <= n; i++) {
if (Col[i] == 1) {
for (auto &x : G1.G[i]) {
Edge tp = G1.E[x];
if (tp.e >= 1 && tp.e <= n && !tp.f) {
}
}
}
}
}*/
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]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
141728 KB |
Output is correct |
| 2 |
Correct |
142 ms |
141924 KB |
Output is correct |
| 3 |
Correct |
149 ms |
142152 KB |
Output is correct |
| 4 |
Correct |
148 ms |
142900 KB |
Output is correct |
| 5 |
Correct |
154 ms |
143132 KB |
Output is correct |
| 6 |
Correct |
148 ms |
143784 KB |
Output is correct |
| 7 |
Correct |
155 ms |
144096 KB |
Output is correct |
| 8 |
Correct |
148 ms |
144156 KB |
Output is correct |
| 9 |
Correct |
159 ms |
144440 KB |
Output is correct |
| 10 |
Correct |
151 ms |
144440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
141728 KB |
Output is correct |
| 2 |
Correct |
142 ms |
141924 KB |
Output is correct |
| 3 |
Correct |
149 ms |
142152 KB |
Output is correct |
| 4 |
Correct |
148 ms |
142900 KB |
Output is correct |
| 5 |
Correct |
154 ms |
143132 KB |
Output is correct |
| 6 |
Correct |
148 ms |
143784 KB |
Output is correct |
| 7 |
Correct |
155 ms |
144096 KB |
Output is correct |
| 8 |
Correct |
148 ms |
144156 KB |
Output is correct |
| 9 |
Correct |
159 ms |
144440 KB |
Output is correct |
| 10 |
Correct |
151 ms |
144440 KB |
Output is correct |
| 11 |
Correct |
321 ms |
156740 KB |
Output is correct |
| 12 |
Correct |
582 ms |
195292 KB |
Output is correct |
| 13 |
Correct |
984 ms |
206132 KB |
Output is correct |
| 14 |
Correct |
735 ms |
206132 KB |
Output is correct |
| 15 |
Correct |
213 ms |
206132 KB |
Output is correct |
| 16 |
Correct |
1305 ms |
231424 KB |
Output is correct |
| 17 |
Correct |
1418 ms |
231700 KB |
Output is correct |
| 18 |
Correct |
1300 ms |
260216 KB |
Output is correct |
| 19 |
Correct |
858 ms |
260216 KB |
Output is correct |
| 20 |
Correct |
340 ms |
260216 KB |
Output is correct |
