Submission #72206

#	Time	Username	Problem	Language	Result	Execution time	Memory
72206		(#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	361 ms	46668 KiB

aqua

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll inf = 900LL*900*900*900+9;

int dx[4] = {-1,0,0,1}, dy[4] = {0,1,-1,0};

inline int sq(int x) {
  return x*x;
}

char fl[909][909];
long long dist[909][909];
int g[909][909][4][3];
int n;

int main() {
  scanf("%d",&n);
  int sy, sx, ey, ex;
  for(int i=0;i<n;i++) {
    scanf("%s",fl[i]);
    for(int j=0;j<n;j++) {
      if(fl[i][j] == 'M') {
        sy = i;
        sx = j;
        fl[i][j] = '.';
      } else if(fl[i][j] == 'H') {
        ey = i;
        ex = j;
        fl[i][j] = '.';
      }
    }
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<4;k++) {
        g[i][j][k][0] = -1;
        g[i][j][k][1] = -2;
      }
  // UP DOWN
  for(int j=0;j<n;j++) {
    int pl=0, pr=-1,cl=0;
    bool bl = true;
    for(int i=0;i<n;i++) {
      if(bl) {
        if(fl[i][j] == 'W') continue;
        bl = false;
        cl = i;
      } else {
        if(fl[i][j] == '.') continue;
        int cost = sq(cl-pr-1);
        int cr = i-1;
        for(int k=pl;k<=pr;k++) {
          g[k][j][1][0] = cl;
          g[k][j][1][1] = cr;
          g[k][j][1][2] = cost;
        }
        for(int k=cl;k<=cr;k++) {
          g[k][j][2][0] = pl;
          g[k][j][2][1] = pr;
          g[k][j][2][2] = cost;
        }
        pl = cl;
        pr = cr;
        bl = true;
      }
    }
    if(!bl) {
      int cost = sq(cl-pr-1);
      int cr = n-1;
      for(int k=pl;k<=pr;k++) {
        g[k][j][1][0] = cl;
        g[k][j][1][1] = cr;
        g[k][j][1][2] = cost;
      }
      for(int k=cl;k<=cr;k++) {
        g[k][j][2][0] = pl;
        g[k][j][2][1] = pr;
        g[k][j][2][2] = cost;
      }
    }
  }
  // LEFT RIGHT
  for(int i=0;i<n;i++) {
    int pl=0, pr=-1,cl=0;
    bool bl = true;
    for(int j=0;j<n;j++) {
      if(bl) {
        if(fl[i][j] == 'W') continue;
        bl = false;
        cl = j;
      } else {
        if(fl[i][j] == '.') continue;
        int cost = sq(cl-pr-1);
        int cr = j-1;
        for(int k=pl;k<=pr;k++) {
          g[i][k][3][0] = cl;
          g[i][k][3][1] = cr;
          g[i][k][3][2] = cost;
        }
        for(int k=cl;k<=cr;k++) {
          g[i][k][0][0] = pl;
          g[i][k][0][1] = pr;
          g[i][k][0][2] = cost;
        }
        pl = cl;
        pr = cr;
        bl = true;
      }
    }
    if(!bl) {
      int cost = sq(cl-pr-1);
      int cr = n-1;
      for(int k=pl;k<=pr;k++) {
        g[i][k][3][0] = cl;
        g[i][k][3][1] = cr;
        g[i][k][3][2] = cost;
      }
      for(int k=cl;k<=cr;k++) {
        g[i][k][0][0] = pl;
        g[i][k][0][1] = pr;
        g[i][k][0][2] = cost;
      }
    }
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      dist[i][j] = inf;
  dist[sy][sx] = 0;
  priority_queue<tuple<ll, int, int>> pq;
  pq.emplace(0,sy,sx);
  while(!pq.empty()) {
//    auto [w,y,x] = pq.top();
    ll w;
    int y,x;
    tie(w,y,x) = pq.top();
    if(y == ey && x == ex) break;
    pq.pop();
    w = -w;
    if(w != dist[y][x]) continue;
    for(int k=0;k<4;k++) {
      if(k == 0 || k == 3) {
        for(int xx = g[y][x][k][0]; xx<=g[y][x][k][1]; xx++) {
          ll ww = w + g[y][x][k][2];
          if(dist[y][xx] <= ww) continue;
          dist[y][xx] = ww;
          pq.emplace(-ww,y,xx);
        }
      } else {
        for(int yy = g[y][x][k][0]; yy<=g[y][x][k][1]; yy++) {
          ll ww = w + g[y][x][k][2];
          if(dist[yy][x] <= ww) continue;
          dist[yy][x] = ww;
          pq.emplace(-ww,yy,x);
        }
      }
    }
  }
  if(dist[ey][ex] == inf) puts("-1");
  else printf("%lld\n",dist[ey][ex]);
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
aqua.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",fl[i]);
     ~~~~~^~~~~~~~~~~~
aqua.cpp:139:5: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(y == ey && x == ex) break;
     ^~
aqua.cpp:139:16: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(y == ey && x == ex) break;
        ~~~~~~~~^~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64