Submission #72370

#TimeUsernameProblemLanguageResultExecution timeMemory
72370IDxTree (#118)Aquatic Labyrinth (FXCUP3_aqua)C++17
0 / 100
86 ms97508 KiB
#include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef long long ll; typedef pair<ll,int> pli; typedef pair<int,int> pii; const int mx = 909; const ll inf = 1e15; 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]; ll 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, cur2; for(int i = 0; i < n; i++) { d = 1; cur = -1; cur2 = -1; for(int j = 0; j < n; j++) { if(S[i][j] != 'W') { if(cur != -1) { if(cur2 != j-1) { //printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2); for(int f = cur; f <= cur2; f++) G[e(i,f,0)].emplace_back(e(i,j,d),(j-cur2-1)*(j-cur2-1)); cur = cur2 = j; } else { G[e(i,cur2,d)].emplace_back(e(i,j,d),0); cur2 = j; } } else cur = cur2 = j; } } d = 2; cur = -1; cur2 = -1; for(int j = n - 1; j >= 0; j--) { if(S[i][j] != 'W') { if(cur != -1) { if(cur2 != j+1) { //printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2); for(int f = cur2; f <= cur; f++) G[e(i,f,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1)); cur = cur2 = j; } else { G[e(i,cur2,d)].emplace_back(e(i,j,d),0); cur2 = j; } } else cur = cur2 = j; } } } for(int j = 0; j < n; j++) { d = 3; cur = -1; cur2 = -1; for(int i = 0; i < n; i++) { if(S[i][j] != 'W') { if(cur != -1) { if(cur2 != i-1) { //printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2); for(int f = cur; f <= cur2; f++) G[e(f,j,0)].emplace_back(e(i,j,d),(i-cur2-1)*(i-cur2-1)); cur = cur2 = i; } else { G[e(cur2,j,d)].emplace_back(e(i,j,d),0); cur2 = i; } } else cur = cur2 = i; } } d = 4; cur = -1; cur2 = -1; for(int i = n-1; i >= 0; i--) { if(S[i][j] != 'W') { if(cur != -1) { if(cur2 != i+1) { //printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2); for(int f = cur2; f <= cur; f++) G[e(f,j,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1)); cur = cur2 = i; } else { G[e(cur2,j,d)].emplace_back(e(i,j,d),0); cur2 = i; } } else cur = cur2 = i; } } } } priority_queue<pli,vector<pli>,greater<pli>> 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()) { pli t = pq.top(); pq.pop(); if(t.va > dist[t.vb]) continue; for(pii &p : G[t.vb]) { ll tmp = dist[t.vb] + p.vb; ////printf("tmp = %d, now = %d, dist[%d] = %d\n",tmp,t.vb,p.va,dist[p.va]); //system("pause"); if(dist[p.va] > tmp) { dist[p.va] = tmp; pq.emplace(dist[p.va], p.va); } } } ll 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)]) { if(p.va % sq == 2) 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("%2lld ",dist[e(i,j,0)]<inf?dist[e(i,j,0)]:-1LL); } puts(""); } } int main() { //freopen("sample.txt","rt",stdin); input(); dijk(); //debug(); }

Compilation message (stderr)

aqua.cpp: In function 'void input()':
aqua.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%*c%s",S[i]);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...