제출 #72399

#제출 시각아이디문제언어결과실행 시간메모리
72399ㅋ (#118)수중 미로 (FXCUP3_aqua)C++17
100 / 100
619 ms164712 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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]);
         ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...