Submission #942939

#	Time	Username	Problem	Language	Result	Execution time	Memory
942939		beepbeepsheep	Portals (BOI14_portals)	C++17	70 / 100	1069 ms	130960 KiB

portals

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

#define ll long long
#define ii pair<ll,ll>

const ll maxn=1005;
char grid[maxn][maxn];
ll dis[maxn][maxn];
ii wall[maxn][maxn][4]; //N,E,S,W
ll hasWall[maxn][maxn];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll r,c;
    ii s,e;
    cin>>r>>c;
    for (int i=0;i<=r+1;i++){
        for (int j=0;j<=c+1;j++){
            grid[i][j]='#';
        }
    }
    for (int i=1;i<=r;i++){
        for (int j=1;j<=c;j++){
            cin>>grid[i][j];
            if (grid[i][j]=='S') s={i,j};
            if (grid[i][j]=='C') e={i,j};
        }
    }
    memset(dis,63,sizeof(dis));
    memset(hasWall,63,sizeof(hasWall));
    for (int i=1;i<=r;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=0;j<=c+1;j++){
            if (grid[i][j]=='#')
                p={i,j+1},cnt=0;
            else{
                wall[i][j][0]=p;
                cnt++;
                hasWall[i][j]=min(hasWall[i][j],cnt);
            }
            //first open square
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=0;j<=r+1;j++){
            if (grid[j][i]=='#'){
                p={j+1,i},cnt=0;
            }
            else{
                cnt++;
                wall[j][i][1]=p;
                hasWall[j][i]=min(hasWall[j][i],cnt);
            }
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=c+1;j>=0;j--){
            if (grid[i][j]=='#')
                p={i,j-1}, cnt=0;
            else{
                cnt++;
                wall[i][j][2]=p;
                hasWall[i][j]=min(hasWall[i][j],cnt);
            }
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        ll cnt=0;
        for (int j=r+1;j>=0;j--){
            if (grid[j][i]=='#'){
                p={j-1,i};
                cnt=0;
            }
            else{
                cnt++;
                wall[j][i][3]=p;
                hasWall[j][i]=min(hasWall[j][i],cnt);
            }
        }
    }
    priority_queue<pair<ll,ii>,vector<pair<ll,ii>>,greater<pair<ll,ii>>> pq;
    pq.emplace(0,make_pair(s.first,s.second));
    while (pq.size()){
        ll d,x,y;
        ii p;
        tie(d,p)=pq.top();
        tie(x,y)=p;
        pq.pop();
        //cerr<<d<<' '<<x<<' '<<y<<endl;
        if (dis[x][y]<=d) continue;
        dis[x][y]=d;
        for (int i=0;i<4;i++){
            ll nx=wall[x][y][i].first,ny=wall[x][y][i].second;
            if (dis[nx][ny]<=d+hasWall[x][y]) continue;
            pq.emplace(d+hasWall[x][y],make_pair(nx,ny));
        }
        for (int i=0;i<4;i++){
            ll nx=x+dx[i],ny=y+dy[i];
            if (grid[nx][ny]=='#') continue;
            if (dis[nx][ny]<=d+1) continue;
            pq.emplace(d+1,make_pair(nx,ny));
        }
    }
    cout<<dis[e.first][e.second];
    return 0;
}

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