Submission #1217411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217411		i_love_spring	Portals (BOI14_portals)	C++20	0 / 100	8 ms	16276 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define int long long
const int N = 1005,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],dw[N][N];
ar<int,2> rht[N][N],lft[N][N],down[N][N],up[N][N];
char a[N][N];
bool valid(int x,int y) {
  return (x > 0 && y > 0 && x <= n && y <= m);
}
void comp(){
  // left & right
  for (int i = 1; i <= n;i++) {
    int x,y;
    x = y = -1;
    // left
    for (int j = m; j > 0;j--) {
      if (a[i][j] == '#') x = y = -1;
      else if (x == -1) x = i, y = j;
      lft[i][j] = {x,y};
    }

    //right
    x = y = -1;
    for (int j = 1; j <= m;j++) {
      if (a[i][j] == '#') x = y = -1;
      else if (x == -1) x = i , y = j;
      rht[i][j] = {x,y};
    }
  }
  for (int j = 1; j <= m;j++) {
    int x,y;
    x = y = -1;
    // up
    for (int i = n; i > 0;i--) {
      if (a[i][j] == '#') x = y = -1;
      else if (x == -1) x = i , y = j;
      up[i][j] = {x,y};
    }
    
    // down 
    x = y = -1;
    for (int i = 1; i <= n;i++) {
      if (a[i][j] == '#') x = y = -1;
      else if (x == -1) x = i , y = j;
      down[i][j] = {x,y};
    }
  }
}
void bfs() {
  queue<ar<int,2>> q;
  memset(dw,inf,sizeof(dw));
  for (int i = 1; i <= n;i++) {
    for (int j = 1; j <= m;j++) {
      if (a[i][j] == '#') continue;
      for (int dr = 0; dr < 4;dr++) {
        int ni = i + rc[dr] ,nj = j + cc[dr];
        if (valid(ni,nj) && a[ni][nj] == '#') {
          q.push({i,j});
          dw[i][j] = 0;
        }
      }
    }
  }
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    for (int i = 0; i < 4;i++) {
      int nx = x + rc[i] , ny = y + cc[i];
      if (valid(nx,ny) && a[nx][ny] != '#' && dw[nx][ny] > dw[x][y] + 1) {
        q.push({nx,ny});
        dw[nx][ny] = dw[x][y] + 1;
      }
    }
  }
}
void dijkstra() {
  memset(d,inf,sizeof(d));
  priority_queue<ar<int,3>> pq;
  pq.push({0,sx,sy});
  d[sx][sy] = 0;
  
  while (!pq.empty()) {
    auto [w,x,y] = pq.top();
    pq.pop();
    if (-w != d[x][y]) continue;
    for (int i = 0; i < 4; ++i) {
      ar<int,2> next;
      if (i == 0) next = lft[x][y];
      if (i == 1) next = rht[x][y];
      if (i == 2) next = up[x][y];
      if (i == 3) next = down[x][y];

      int nx = next[0], ny = next[1];
      int cost = d[x][y] + dw[x][y] + 1;

      if (valid(nx, ny) && a[nx][ny] != '#' && d[nx][ny] > cost) {
        d[nx][ny] = cost;
        pq.push({-cost, nx, ny});
      }
    }

    for (int i = 0;i < 4;i++) {
      int nx = x + rc[i],ny = y + cc[i];
      int cost = d[x][y] + 1;
      if (valid(nx,ny) && a[nx][ny] != '#' && d[nx][ny] > cost){
        pq.push({-(d[nx][ny] = cost),nx,ny});
      }
    }
  }
}
void solve() {  
  cin >> n >> m;
  for (int i = 1; i <= n;i++) {
    for (int j = 1; 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();
 // cerr << dw[sx][sy];
  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