Submission #21831

#	Time	Username	Problem	Language	Result	Execution time	Memory
21831		ngkan146	Portals (BOI14_portals)	C++14	100 / 100	279 ms	30640 KiB

portals

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int n,m,xs,ys,xe,ye;
string s[1005];
int block[1005][1005][4];
int d[1005][1005], mini[1005][1005];
priority_queue <ii,vector<ii>,greater<ii> > pq;
int prep(){
   iostream::sync_with_stdio(0);
   cin >> n >> m;
   for(int i=1;i<=n;i++)
      cin >> s[i], s[i] = '#' + s[i] + '#';
   for(int i=1;i<=m+3;i++)
      s[0].push_back('#'), s[n+1].push_back('#');
   for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
         if (s[i][j] == 'S') xs = i, ys = j;
         else if (s[i][j] == 'C') xe = i, ye = j;
   }
   for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
         if (s[i][j-1] == '#') block[i][j][3] = j;
         else block[i][j][3] = block[i][j-1][3];
      for(int j=m;j>=1;j--){
         if (s[i][j+1] == '#') block[i][j][1] = j;
         else block[i][j][1] = block[i][j+1][1];
      }
   }
   for(int j=1;j<=m;j++){
      for(int i=1;i<=n;i++)
         if (s[i-1][j] == '#') block[i][j][0] = i;
         else block[i][j][0] = block[i-1][j][0];
      for(int i=n;i>=1;i--)
         if (s[i+1][j] == '#') block[i][j][2] = i;
         else block[i][j][2] = block[i+1][j][2];
   }
   for(int i=0;i<=n+1;i++)
      fill(d[i],d[i]+m+2,(int) 1e9),
      fill(mini[i], mini[i]+m+2,(int) 1e9);
   d[xs][ys] = 0;
}
void prep1(){
   queue <int> q;
   for(int i=0;i<=n+1;i++)
      for(int j=0;j<=m+1;j++)
         if (s[i][j] == '#') mini[i][j] = 0, q.push(i*1005 + j);
   while(q.size()){
      int x = q.front()/1005;
      int y = q.front()%1005;
      q.pop();
      for(int k=0;k<4;k++){
         int X = x + dx[k];
         int Y = y + dy[k];
         if (X < 0 || n+1 < X || Y < 0 || m+1 < Y) continue;
         if (mini[X][Y] == (int) 1e9)
            mini[X][Y] = mini[x][y] + 1,
            q.push(X*1005 + Y);
      }
   }
}
int main(){
   prep();
   prep1();
   pq.push(ii(0, xs * 1005 + ys));
   while(pq.size()){
      int x = pq.top().se/1005;
      int y = pq.top().se%1005;
      pq.pop();
      for(int k=0;k<4;k++){
         int X = x + dx[k];
         int Y = y + dy[k];
         if (s[X][Y] == '#') continue;
         if (d[X][Y] > d[x][y] + 1)
            d[X][Y] = d[x][y] + 1,
            pq.push(ii(d[X][Y], X*1005 + Y));
      }
      if (d[block[x][y][0]][y] > d[x][y] + mini[x][y])
         d[block[x][y][0]][y] = d[x][y] + mini[x][y],
         pq.push(ii(d[x][y] + mini[x][y], block[x][y][0]*1005 + y));
      if (d[block[x][y][2]][y] > d[x][y] + mini[x][y])
         d[block[x][y][2]][y] = d[x][y] + mini[x][y],
         pq.push(ii(d[x][y] + mini[x][y],block[x][y][2]*1005 + y));
      if (d[x][block[x][y][1]] > d[x][y] + mini[x][y])
         d[x][block[x][y][1]] = d[x][y] + mini[x][y],
         pq.push(ii(d[x][y] + mini[x][y],x*1005 + block[x][y][1]));
      if (d[x][block[x][y][3]] > d[x][y] + mini[x][y])
         d[x][block[x][y][3]] = d[x][y] + mini[x][y],
         pq.push(ii(d[x][y] + mini[x][y],x*1005 + block[x][y][3]));
   }
   cout << d[xe][ye];
}
/*
4 4
.#.C
.#.#
....
S...
*/

Compilation message (stderr)

portals.cpp: In function 'int prep()':
portals.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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