Submission #1217335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217335		i_love_spring	Portals (BOI14_portals)	C++20	0 / 100	2 ms	4424 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 1003;
const int inf = 1e9+ 5;
const int rc[]{0,0,1,-1};
const int cc[]{1,-1,0,0}; // right , left, down , up 
int n,m,sx,sy,cx,cy,d[N][N];
ar<int,2> tel[N][N][4],near[N][N][4];
char a[N][N];
void comp() {
  // left & right
  for (int i = 0; i < n;i++) {
    int x,y;
    x = y = -1;
    for (int j = m - 1; j >= 0;j--) {
      tel[i][j][1] = {x,y};
      if (a[i][j] == '#') {
        x = i , y = j;
      }
    }
    x = y = -1;
    for (int j = 0; j < m;j++) {
      tel[i][j][0] = {x,y};
      if (a[i][j] == '#') x = i, y = j;
    }
  }
  // up & down 
  for (int j = 0; j < m;j++) {
    int x,y;
    x = y = -1;
    for (int i = n - 1; i >= 0;i--) {
      tel[i][j][3] = {x,y};
      if (a[i][j] == '#') x = i, y = j;
    }
    x = y = -1;
    for (int i = 0; i < n;i++) {
      tel[i][j][2] = {x,y};
      if (a[i][j] == '#') x = i, y = j;
    }
  }
}
bool valid(int x,int y) {
  return (x >= 0 && y >= 0 && x < n && y < m);
}
void bfs() {
  queue<ar<int,3>> q;
  for (int i = 0; i < n;i++) {
    for (int j = 0; j < m;j++) {
      for (int t = 0; t < 4;t++) near[i][j][t] = {-1,-1};
      if (a[i][j] == '#') continue;
      for (int t = 0; t < 4; t++) {
        int ni = i + rc[t],nj = j + cc[t];
        if (valid(ni,nj) && a[ni][nj] == '#') {
          q.push({i,j,t});
          near[i][j][t] = {ni,nj}; 
        }
      }
    }
  }
  while (!q.empty()) {
    auto [x,y,t] = q.front();
    q.pop();
    if (valid(x + rc[t ^ 1],y + cc[t ^ 1]) && a[x + rc[t ^ 1]][y + cc[t ^ 1]] != '#') {
      near[x + rc[t ^ 1]][y + cc[t ^ 1]][t] = near[x][y][t];
      q.push({x + rc[t ^ 1],y + cc[t ^ 1],t});
    }
  }
}
void dijkstra() {
  memset(d,inf,sizeof(d));
  d[sx][sy] = 0;
  priority_queue<ar<int,3>> pq;
  pq.push({0,sx,sy});
  while (!pq.empty()) {
    auto [w,x,y] = pq.top();
    pq.pop();
    if (-w != d[x][y]) continue;
    for (int i = 0; i < 4;i++) {
      int nx = x + rc[i], ny = y + cc[i];
      if (valid(nx,ny) && a[nx][ny] != '#' && d[nx][ny] > d[x][y] + 1) {
        pq.push({-(d[nx][ny] = d[x][y] + 1),nx,ny});
      }
    }
    for (int i = 0; i < 4;i++) {
      auto [wx, wy] =  near[x][y][i];
      if (valid(wx,wy)) {
        for (int j = 0; j < 4;j++) {
          auto [nx, ny] = tel[wx][wy][j];
          if (valid(nx, ny) && d[nx][ny] > d[x][y] + 1 + abs(wx - x) + abs(wy - y)) {
            pq.push({-(d[nx][ny] = d[x][y] + abs(wx - x) + abs(wy - y)),nx,ny});
          } 
        }
      }
    }
  }
}
void solve() {  
  cin >> n >> m;
  for (int i = 0; i < n;i++) {
    for (int j = 0; j < m;j++) {
      cin >> a[i][j];
      if (a[i][j] == 'S') sx = i, sy = j;
      if (a[i][j] == 'C') cx = i, cy = j;
    }
  } 
  comp();
  bfs();
  dijkstra();
  cout << d[cx][cy];
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
 // cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

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