Submission #287272

#	Time	Username	Problem	Language	Result	Execution time	Memory
287272		AlexLuchianov	Portals (BOI14_portals)	C++14	100 / 100	479 ms	52616 KiB

portals

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <queue>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2000;
int const inf = nmax * nmax;
std::string mat[1 + nmax];
int n, m;
bool valid(int x, int y) {
  return 0 <= x && x < n && 0 <= y && y < m;
}

int const iplus[4] = {0, 0, 1, -1};
int const jplus[4] = {1, -1, 0, 0};
int dist[1 + nmax][1 + nmax];

int fast[4][1 + nmax][1 + nmax];

void precompute() {
  std::queue<std::pair<int,int>> q;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      dist[i][j] = inf;
      if(mat[i][j] != '#') {
        for(int h = 0; h < 4; h++) {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) == 0 || mat[newx][newy] == '#') {
            dist[i][j] = 1;
            q.push({i, j});
          }
        }
      }
    }

  while(0 < q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for(int h = 0; h < 4; h++) {
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(valid(newx, newy) == 1 && mat[newx][newy] != '#' && dist[newx][newy] == inf) {
        q.push({newx, newy});
        dist[newx][newy] = dist[x][y] + 1;
      }
    }
  }

  for(int h = 0; h < 4; h++) {
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        if(mat[i][j] != '#') {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) && mat[newx][newy] != '#')
            fast[h][i][j] = fast[h][newx][newy] + 1;
        }
    for(int i = n - 1; 0 <= i; i--)
      for(int j = m - 1; 0 <= j; j--)
        if(mat[i][j] != '#') {
          int newx = i + iplus[h];
          int newy = j + jplus[h];
          if(valid(newx, newy) && mat[newx][newy] != '#')
            fast[h][i][j] = fast[h][newx][newy] + 1;
        }
  }
}

struct State{
  int x;
  int y;
  int cost;
  bool operator < (State const a) const {
    return a.cost < cost;
  }
};
int dp[1 + nmax][1 + nmax];

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  std::cin >> n >> m;
  for(int i = 0; i < n; i++)
    std::cin >> mat[i];
  int x, y;
  int x2, y2;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      if(mat[i][j] == 'S') {
        x = i;
        y = j;
      } else if(mat[i][j] == 'C') {
        x2 = i;
        y2 = j;
      }
  precompute();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      dp[i][j] = inf;

  std::priority_queue<State> pq;
  dp[x][y] = 0;
  pq.push({x, y, 0});

  while(0 < pq.size()) {
    int x = pq.top().x;
    int y = pq.top().y;
    int cost = pq.top().cost;
    pq.pop();
    if(cost == dp[x][y]) {
      for(int h = 0; h < 4; h++) {
        int newx = x + iplus[h];
        int newy = y + jplus[h];
        if(valid(newx, newy) && mat[newx][newy] != '#') {
          if(dp[x][y] + 1 < dp[newx][newy]) {
            dp[newx][newy] = dp[x][y] + 1;
            pq.push({newx, newy, dp[newx][newy]});
          }
        }
        newx = x + iplus[h] * fast[h][x][y];
        newy = y + jplus[h] * fast[h][x][y];
        if(valid(newx, newy) && mat[newx][newy] != '#') {
          if(dp[x][y] + dist[x][y] < dp[newx][newy]) {
            dp[newx][newy] = dp[x][y] + dist[x][y];
            pq.push({newx, newy, dp[newx][newy]});
          }
        }
      }
    }
  }
  std::cout << dp[x2][y2];
  return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:140:25: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |   std::cout << dp[x2][y2];
      |                         ^
portals.cpp:140:25: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:112:10: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |   pq.push({x, y, 0});
      |   ~~~~~~~^~~~~~~~~~~
portals.cpp:112:10: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30