Submission #72265

#TimeUsernameProblemLanguageResultExecution timeMemory
72265IDxTree (#118)Aquatic Labyrinth (FXCUP3_aqua)C++17
0 / 100
96 ms97528 KiB
#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; 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; } } } 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; 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; } } } } 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, dist[%d] = %d\n",tmp,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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...