#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
const int mx = 909;
const ll inf = 1e15;
int n, sq;
int e(int i, int j, int v)
{
return v * sq + i * n + j;
}
int e(int x, int v)
{
return v * sq + x;
}
void d(int v)
{
//printf("%d %d %d",v%n,(v%sq)/n,v/sq);
}
bool ok(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < n;
}
char S[mx][mx];
vector<pii> G[5*mx*mx];
ll dist[5*mx*mx];
int M, H;
void input()
{
scanf("%d",&n);
sq = n * n;
for(int i = 0; i < n; i++)
scanf("%*c%s",S[i]);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(S[i][j] == 'M')
M = e(i,j,0);
if(S[i][j] == 'H')
H = e(i,j,0);
if(S[i][j] == 'W')
continue;
for(int t = 1; t <= 4; t++)
{
G[e(i,j,t)].emplace_back(e(i,j,0),0);
}
}
}
int d = 0, cur, cur2;
for(int i = 0; i < n; i++)
{
d = 1;
cur = -1;
cur2 = -1;
for(int j = 0; j < n; j++)
{
if(S[i][j] != 'W')
{
if(cur != -1)
{
if(cur2 != j-1)
{
//printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2);
for(int f = cur; f <= cur2; f++)
G[e(i,f,0)].emplace_back(e(i,j,d),(j-cur2-1)*(j-cur2-1));
cur = cur2 = j;
}
else
{
G[e(i,cur2,d)].emplace_back(e(i,j,d),0);
cur2 = j;
}
}
else cur = cur2 = j;
}
}
d = 2;
cur = -1; cur2 = -1;
for(int j = n - 1; j >= 0; j--)
{
if(S[i][j] != 'W')
{
if(cur != -1)
{
if(cur2 != j+1)
{
//printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2);
for(int f = cur2; f <= cur; f++)
G[e(i,f,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1));
cur = cur2 = j;
}
else
{
G[e(i,cur2,d)].emplace_back(e(i,j,d),0);
cur2 = j;
}
}
else cur = cur2 = j;
}
}
}
for(int j = 0; j < n; j++)
{
d = 3;
cur = -1;
cur2 = -1;
for(int i = 0; i < n; i++)
{
if(S[i][j] != 'W')
{
if(cur != -1)
{
if(cur2 != i-1)
{
//printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2);
for(int f = cur; f <= cur2; f++)
G[e(f,j,0)].emplace_back(e(i,j,d),(i-cur2-1)*(i-cur2-1));
cur = cur2 = i;
}
else
{
G[e(cur2,j,d)].emplace_back(e(i,j,d),0);
cur2 = i;
}
}
else cur = cur2 = i;
}
}
d = 4;
cur = -1;
cur2 = -1;
for(int i = n-1; i >= 0; i--)
{
if(S[i][j] != 'W')
{
if(cur != -1)
{
if(cur2 != i+1)
{
//printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2);
for(int f = cur2; f <= cur; f++)
G[e(f,j,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1));
cur = cur2 = i;
}
else
{
G[e(cur2,j,d)].emplace_back(e(i,j,d),0);
cur2 = i;
}
}
else cur = cur2 = i;
}
}
}
}
priority_queue<pli,vector<pli>,greater<pli>> pq;
void dijk()
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int d = 0; d <= 4; d++)
dist[e(i,j,d)] = inf;
dist[M] = 0;
pq.emplace(0,M);
while(!pq.empty())
{
pli t = pq.top();
pq.pop();
if(t.va > dist[t.vb])
continue;
for(pii &p : G[t.vb])
{
ll tmp = dist[t.vb] + p.vb;
////printf("tmp = %d, now = %d, dist[%d] = %d\n",tmp,t.vb,p.va,dist[p.va]);
//system("pause");
if(dist[p.va] > tmp)
{
dist[p.va] = tmp;
pq.emplace(dist[p.va], p.va);
}
}
}
ll ans = inf;
for(int t = 0; t <= 4; t++)
{
ans = min(ans, dist[e(H,t)]);
}
cout << (ans == inf ? -1 : ans) << '\n';
}
void debug()
{
for(int k = 0; k < 5; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
//for(int k = 0; k < 5; k++)
{
for(pii &p : G[e(i,j,k)])
{
if(p.va % sq == 2)
printf("%d -> %d, cost = %d\n",e(i,j,k),p.va,p.vb);
}
}
}
}
}
printf("M = %d, H = %d\n",M,H);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
printf("%2lld ",dist[e(i,j,0)]<inf?dist[e(i,j,0)]:-1LL);
}
puts("");
}
}
int main()
{
//freopen("sample.txt","rt",stdin);
input();
dijk();
//debug();
}
Compilation message
aqua.cpp: In function 'void input()':
aqua.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%*c%s",S[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
97272 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
97508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
97272 KB |
Output is correct |
| 2 |
Incorrect |
85 ms |
97508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
