#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
const int mx = 909, inf = 1e9;
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];
int 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;
for(int i = 0; i < n; i++){
d = 1;
cur = -1;
for(int j = 0; j < n; j++){
if(S[i][j] != 'W'){
if(cur != -1){
if(cur != j-1) G[e(i,cur,0)].emplace_back(e(i,j,d),(j-cur-1)*(j-cur-1));
else G[e(i,cur,d)].emplace_back(e(i,j,d),0);
}
cur = j;
}
}
d = 2; cur = -1;
for(int j = n - 1; j >= 0; j--){
if(S[i][j] != 'W'){
if(cur != -1){
if(cur != j+1) G[e(i,cur,0)].emplace_back(e(i,j,d),(cur-j-1)*(cur-j-1));
else G[e(i,cur,d)].emplace_back(e(i,j,d),0);
}
cur = j;
}
}
}
for(int j = 0; j < n; j++){
d = 3; cur = -1;
for(int i = 0; i < n; i++){
if(S[i][j] != 'W'){
if(cur != -1){
if(cur != i-1) G[e(cur,j,0)].emplace_back(e(i,j,d),(i-cur-1)*(i-cur-1));
else G[e(cur,j,d)].emplace_back(e(i,j,d),0);
}
cur = i;
}
}
d = 4; cur = -1;
for(int i = n - 1; i >= 0; i--){
if(S[i][j] != 'W'){
if(cur != -1){
if(cur != i+1) G[e(cur,j,0)].emplace_back(e(i,j,d),(cur-i-1)*(cur-i-1));
else G[e(cur,j,d)].emplace_back(e(i,j,d),0);
}
cur = i;
}
}
}
}
priority_queue<pii,vector<pii>,greater<pii>> 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()){
pii t = pq.top(); pq.pop();
if(t.va > dist[t.vb]) continue;
for(pii &p : G[t.vb]){
int 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);
}
}
}
int 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)])
{
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("%d ",dist[e(i,j,0)]<inf?:-1);
}
puts("");
}
}
int main(){
//freopen("sample.txt","rt",stdin);
input();
dijk();
//debug();
}
Compilation message
aqua.cpp: In function 'void debug()':
aqua.cpp:142:45: warning: the omitted middle operand in ?: will always be 'true', suggest explicit middle operand [-Wparentheses]
printf("%d ",dist[e(i,j,0)]<inf?:-1);
^
aqua.cpp: In function 'void input()':
aqua.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua.cpp:34:37: 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("%*c%s",S[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
97276 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
97372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
97276 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
97372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
