#include<bits/stdc++.h>
int ex,ey,n,w,a[1010][1010],b[1010][1010],cnt[1010][1010],sx,sy;
char s[1010][1010];
using namespace std;
# define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// This class represents a directed graph using
// adjacency list representation
class Graph
{
int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list< pair<int, int> > *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v, int w);
// prints shortest path from s
void shortestPath(int s);
};
// Allocates memory for adjacency list
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair> [V];
}
void Graph::addEdge(int u, int v, int w)
{
if(w==0)
{
u=u;
}
adj[u].push_back(make_pair(v, w));
}
// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
// Create a priority queue to store vertices that
// are being preprocessed. This is weird syntax in C++.
// Refer below link for details of this syntax
// https://www.geeksforgeeks.org/implement-min-heap-using-stl/
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
vector<int> dist(V, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
// 'i' is used to get all adjacent vertices of a vertex
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
// Get vertex label and weight of current adjacent
// of u.
int v = (*i).first;
int weight = (*i).second;
// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight)
{
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// Print shortest distances stored in dist[]
int ans=min(dist[a[ex][ey]],dist[b[ex][ey]]);
if(ans==INF) printf("-1");
else printf("%d",ans);
}
// Driver program to test methods of graph class
int pa[4000010],pb[4000010],sav[4000010];
int main()
{
//freopen("input.txt","r",stdin);
int i,j;
// create the graph given in above fugure
int V,sw,sw2;
scanf("%d",&n);
V=n*n*2;
Graph g(n*n*2);
for(i=1;i<=n;i++)
{
scanf("%s",s[i]);
for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
for(j=1;j<=n;j++)
{
if(s[i][j]=='M') sx=i, sy=j, s[i][j]='.';
if(s[i][j]=='H') ex=i, ey=j, s[i][j]='.';
}
}
for(i=1;i<=n;i++)
{
sw=0; sw2=0;
for(j=1;j<=n;j++)
{
if(s[i][j]=='.' && s[i][j-1]!='.')
{
sw++;
w++;
pa[w]=i;
if(sw>=2){g.addEdge(w-1,w,cnt[i][j-1]*cnt[i][j-1]); g.addEdge(w,w-1,cnt[i][j-1]*cnt[i][j-1]); sav[w]=cnt[i][j-1]*cnt[i][j-1];}
}
if(s[i][j]=='.') a[i][j]=w;
if(s[i][j]=='W') cnt[i][j]=cnt[i][j-1]+1;
}
}
memset(cnt,0,sizeof cnt);
for(j=1;j<=n;j++)
{
sw=0; sw2=0;
for(i=1;i<=n;i++)
{
if(s[i][j]=='.' && s[i-1][j]!='.')
{
sw++; w++; pb[w]=j;
if(sw>=2){g.addEdge(w-1,w,cnt[i-1][j]*cnt[i-1][j]); g.addEdge(w,w-1,cnt[i-1][j]*cnt[i-1][j]); sav[w]=cnt[i-1][j]*cnt[i-1][j];}
}
if(s[i][j]=='.') b[i][j]=w;
if(s[i][j]=='W') cnt[i][j]=cnt[i-1][j]+1;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(s[i][j]=='.')
{
if(pa[a[i][j]]==pa[a[i][j]-1]) g.addEdge(b[i][j],a[i][j]-1,sav[a[i][j]]);
if(pa[a[i][j]]==pa[a[i][j]+1]) g.addEdge(b[i][j],a[i][j]+1,sav[a[i][j]+1]);
if(pb[b[i][j]]==pb[b[i][j]-1]) g.addEdge(a[i][j],b[i][j]-1,sav[b[i][j]]);
if(pb[b[i][j]]==pb[b[i][j]+1]) g.addEdge(a[i][j],b[i][j]+1,sav[b[i][j]+1]);
}
}
}
int c=0;
for(i=sy+1;i<=n;i++)
{
if(s[sx][i]=='.' && s[sx][i-1]=='W') g.addEdge(0,a[sx][i],c*c);
if(s[sx][i]=='W') c++;
}
c=0;
for(i=sy-1;i>=1;i--)
{
if(s[sx][i]=='.' && s[sx][i+1]=='W') g.addEdge(0,a[sx][i],c*c);
if(s[sx][i]=='W') c++;
}
c=0;
for(i=sx+1;i<=n;i++)
{
if(s[i][sy]=='.' && s[i-1][sy]=='W') g.addEdge(0,b[i][sy],c*c);
if(s[i][sy]=='W') c++;
}
c=0;
for(i=sx-1;i>=1;i--)
{
if(s[i][sy]=='.' && s[i+1][sy]=='W') g.addEdge(0,b[i][sy],c*c);
if(s[i][sy]=='W') c++;
}
g.shortestPath(0);
return 0;
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:104:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
^~~
aqua.cpp:104:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(j=n;j>=1;j--) s[i][j]=s[i][j-1]; s[i][0]=0;
^
aqua.cpp:97:9: warning: variable 'V' set but not used [-Wunused-but-set-variable]
int V,sw,sw2;
^
aqua.cpp:97:14: warning: variable 'sw2' set but not used [-Wunused-but-set-variable]
int V,sw,sw2;
^~~
aqua.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s[i]);
~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4672 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5424 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6388 KB |
Output is correct |
| 7 |
Correct |
11 ms |
6900 KB |
Output is correct |
| 8 |
Correct |
12 ms |
6944 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7328 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7328 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4672 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5424 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5672 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6388 KB |
Output is correct |
| 7 |
Correct |
11 ms |
6900 KB |
Output is correct |
| 8 |
Correct |
12 ms |
6944 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7328 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7328 KB |
Output is correct |
| 11 |
Correct |
77 ms |
24464 KB |
Output is correct |
| 12 |
Correct |
224 ms |
75540 KB |
Output is correct |
| 13 |
Correct |
434 ms |
97872 KB |
Output is correct |
| 14 |
Correct |
300 ms |
97872 KB |
Output is correct |
| 15 |
Correct |
52 ms |
97872 KB |
Output is correct |
| 16 |
Correct |
619 ms |
136292 KB |
Output is correct |
| 17 |
Correct |
617 ms |
136292 KB |
Output is correct |
| 18 |
Correct |
583 ms |
164712 KB |
Output is correct |
| 19 |
Correct |
350 ms |
164712 KB |
Output is correct |
| 20 |
Correct |
61 ms |
164712 KB |
Output is correct |
