#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
}
string grid[911];
int n=0;
int gid(int i, int j, int dir){
// S R L D U
return 5*(n*i+j)+dir;
}
char destruct(int v){
int dir = v%5; v/= 5;
int i = v/n, j = v%n;
cout<<'('<<i<<' '<<j<<' '<<dir<<')';
return ' ';
}
// 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 ";
//cout<<destruct(a);
//cout<<destruct(b);
//cout<<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);}
}
T dijkstra(int v, int u){
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[u];
}
};
int main(){OJize();
// Get the grid
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(5*n*n);
// Landing
for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(grid[i][j] != 'W'){
for(int d=1; d<=4; d++) G.connect(gid(i,j,d), gid(i,j,0), 0);
}
// Right
int dir = 1;
for(int i=0; i<n; i++){
int memo1 = -1;
int j = 0;
while(j<n && grid[i][j] == 'W') j++;
for(; j<n; j++){
char prev = j==0? 'W':grid[i][j-1];
char curr = grid[i][j];
if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
else if(prev != 'W' && curr == 'W'){
// A new wall
memo1 = -1;
int j2 = j, water = 0;
while(j2<n && grid[i][j2] == 'W') j2++, water++;
for(; j2<n && grid[i][j2] != 'W'; j2++) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
}
else if(prev == 'W' && curr != 'W'){
// A new floor
int j2 = j;
while(j2<n && grid[i][j2] != 'W') j2++;
if(j2 != n) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
}
else memo1 = -1;
}
}
// Left
dir = 2;
for(int i=0; i<n; i++){
int memo1 = -1;
int j = n-1;
while(j>=0 && grid[i][j] == 'W') j--;
for(; j>=0; j--){
char prev = j==n-1? 'W':grid[i][j+1];
char curr = grid[i][j];
if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
else if(prev != 'W' && curr == 'W'){
// A new wall
memo1 = -1;
int j2 = j, water = 0;
while(j2>=0 && grid[i][j2] == 'W') j2--, water++;
for(; j2>=0 && grid[i][j2] != 'W'; j2--) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
}
else if(prev == 'W' && curr != 'W'){
// A new floor
int j2 = j;
while(j2>=0 && grid[i][j2] != 'W') j2--;
if(j2 != -1) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
}
else memo1 = -1;
}
}
// Down
dir = 3;
for(int j=0; j<n; j++){
int memo1 = -1;
int i = 0;
while(i<n && grid[i][j] == 'W') i++;
for(; i<n; i++){
char prev = i==0? 'W':grid[i-1][j];
char curr = grid[i][j];
if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
else if(prev != 'W' && curr == 'W'){
// A new wall
memo1 = -1;
int i2 = i, water = 0;
while(i2<n && grid[i2][j] == 'W') i2++, water++;
for(; i2<n && grid[i2][j] != 'W'; i2++) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
}
else if(prev == 'W' && curr != 'W'){
// A new floor
int i2 = i;
while(i2<n && grid[i2][j] != 'W') i2++;
if(i2 != n) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
}
else memo1 = -1;
}
}
// Up
dir = 4;
for(int j=0; j<n; j++){
int memo1 = -1;
int i = n-1;
while(i>=0 && grid[i][j] == 'W') i--;
for(; i>=0; i--){
char prev = i==n-1? 'W':grid[i+1][j];
char curr = grid[i][j];
if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
else if(prev != 'W' && curr == 'W'){
// A new wall
memo1 = -1;
int i2 = i, water = 0;
while(i2>=0 && grid[i2][j] == 'W') i2--, water++;
for(; i2>=0 && grid[i2][j] != 'W'; i2--) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
}
else if(prev == 'W' && curr != 'W'){
// A new floor
int i2 = i;
while(i2>=0 && grid[i2][j] != 'W') i2--;
if(i2 != -1) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
}
else memo1 = -1;
}
}
ll ans = G.dijkstra(gid(si,sj,0), gid(ei,ej,0));
cout << (ans != INF? ans : -1);
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:18:18: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
return 5*(n*i+j)+dir;
~~~~^~~
aqua.cpp:64:21: note: 'ej' was declared here
int si, sj, ei, ej;
^~
aqua.cpp:18:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
return 5*(n*i+j)+dir;
~^~
aqua.cpp:64:17: note: 'ei' was declared here
int si, sj, ei, ej;
^~
aqua.cpp:18:18: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
return 5*(n*i+j)+dir;
~~~~^~~
aqua.cpp:64:13: note: 'sj' was declared here
int si, sj, ei, ej;
^~
aqua.cpp:18:16: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
return 5*(n*i+j)+dir;
~^~
aqua.cpp:64:9: note: 'si' was declared here
int si, sj, ei, ej;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
3 ms |
692 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
13 ms |
3216 KB |
Output is correct |
| 7 |
Correct |
24 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
25 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
18 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
3 ms |
692 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
13 ms |
3216 KB |
Output is correct |
| 7 |
Correct |
24 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
25 ms |
3900 KB |
Output is correct |
| 9 |
Correct |
18 ms |
3900 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3900 KB |
Output is correct |
| 11 |
Correct |
308 ms |
36296 KB |
Output is correct |
| 12 |
Correct |
704 ms |
114224 KB |
Output is correct |
| 13 |
Correct |
2037 ms |
181000 KB |
Output is correct |
| 14 |
Correct |
1476 ms |
181000 KB |
Output is correct |
| 15 |
Correct |
367 ms |
188628 KB |
Output is correct |
| 16 |
Correct |
2944 ms |
257836 KB |
Output is correct |
| 17 |
Execution timed out |
3036 ms |
257836 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
