#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
cin.tie(NULL); ios_base::sync_with_stdio(false);
#ifdef jh
freopen("input.txt", "r", stdin);
#endif
}
// if you want to use ll, remember to change 0x3f3f3f3f!!
const ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
struct WGraph{
int n; vector<vector<pair<int,T>>> adj;
WGraph(int n): n{n}, adj{vector<vector<pair<int,T>>>(n+1)} {}
void connect(int a, int b, T c){
//cout<<"Connected "<<a<<' '<<b<<' '<<c<<'\n';
adj[a].push_back({b,c});}
void input(int m){
int a,b,c;
for(int i=0;i<m;i++){cin>>a>>b>>c; connect(a,b,c);}
}
vector<T> dijkstra(int v){
set<pair<T,int>> S; S.insert(make_pair(0,v));
vector<T> dist(n+1, INF); dist[v] = 0;
while(!S.empty()){
int v = (*S.begin()).second, u; T c; S.erase(S.begin());
for(auto& uc:adj[v]){
tie(u,c) = uc;
if(dist[u] <= dist[v]+c) continue;
if(dist[u] != INF) S.erase(S.find({dist[u],u}));
dist[u] = dist[v]+c; S.insert({dist[u],u});
}
}
return dist;
}
};
string grid[911];
int main(){OJize();
// Get the grid
int n; cin>>n;
int si, sj, ei, ej;
for(int i=0; i<n; i++){
cin>>grid[i];
for(int j=0; j<n; j++){
if(grid[i][j] == 'M') si = i, sj = j;
if(grid[i][j] == 'H') ei = i, ej = j;
}
}
WGraph<ll> G(n*n);
// Right
for(int i=0; i<n; i++){
int water = 0;
int j1 = 0;
while(j1<n && grid[i][j1] == 'W') j1++;
int j2 = j1;
for(; j1<n; j1++){
if(j1 != j2 && grid[i][j1] != 'W'){G.connect(n*i+j1, n*i+j2, water*water); continue;}
if(grid[i][j1] == 'W') continue;
water = 0;
while(j2<n && grid[i][j2] != 'W') j2++;
while(j2<n && grid[i][j2] == 'W') j2++, water++;
if(j2 == n) break;
G.connect(n*i+j1, n*i+j2, water*water);
}
}
// Left
for(int i=0; i<n; i++){
int water = 0;
int j1 = n-1;
while(j1>=0 && grid[i][j1] == 'W') j1--;
int j2 = j1;
for(; j1>=0; j1--){
if(j1 != j2 && grid[i][j1] != 'W'){G.connect(n*i+j1, n*i+j2, water*water); continue;}
if(grid[i][j1] == 'W') continue;
water = 0;
while(j2>=0 && grid[i][j2] != 'W') j2--;
while(j2>=0 && grid[i][j2] == 'W') j2--, water++;
if(j2 == -1) break;
G.connect(n*i+j1, n*i+j2, water*water);
}
}
// Down
for(int j=0; j<n; j++){
int water = 0;
int i1 = 0;
while(i1<n && grid[i1][j] == 'W') i1++;
int i2 = i1;
for(; i1<n; i1++){
if(i1 != i2 && grid[i1][j] != 'W'){G.connect(n*i1+j, n*i2+j, water*water); continue;}
if(grid[i1][j] == 'W') continue;
water = 0;
while(i2<n && grid[i2][j] != 'W') i2++;
while(i2<n && grid[i2][j] == 'W') i2++, water++;
if(i2 == n) break;
G.connect(n*i1+j, n*i2+j, water*water);
}
}
// Up
for(int j=0; j<n; j++){
int water = 0;
int i1 = n-1;
while(i1>=0 && grid[i1][j] == 'W') i1--;
int i2 = i1;
for(; i1>=0; i1--){
if(i1 != i2 && grid[i1][j] != 'W'){G.connect(n*i1+j, n*i2+j, water*water); continue;}
if(grid[i1][j] == 'W') continue;
water = 0;
while(i2>=0 && grid[i2][j] != 'W') i2--;
while(i2>=0 && grid[i2][j] == 'W') i2--, water++;
if(i2 == -1) break;
G.connect(n*i1+j, n*i2+j, water*water);
}
}
ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
cout << (ans != INF? ans : -1);
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:125:38: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
~~~~^~~
aqua.cpp:125:35: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
~^~~
aqua.cpp:125:24: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
~~~~~~~~~~^~~~~~~~~
aqua.cpp:125:26: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
