Submission #942917

#	Time	Username	Problem	Language	Result	Execution time	Memory
942917		beepbeepsheep	Portals (BOI14_portals)	C++17	20 / 100	6 ms	23600 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
bool 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};
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=0;j<=c+1;j++){
            if (grid[i][j]=='#')
                p={i,j+1},ok=true;
            else{
                wall[i][j][0]=p;
                hasWall[i][j]|=ok;
                ok=false;
            }
            //first open square
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=0;j<=r+1;j++){
            if (grid[j][i]=='#'){
                p={j+1,i},ok=true;
            }
            else{
                wall[j][i][1]=p;
                hasWall[j][i]|=ok;
                ok=false;
            }
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=c+1;j>=0;j--){
            if (grid[i][j]=='#')
                p={i,j-1},ok=true;
            else{
                wall[i][j][2]=p;
                hasWall[i][j]|=ok;
                ok=false;
            }
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=r+1;j>=0;j--){
            if (grid[j][i]=='#'){
                p={j-1,i};
                ok=true;
            }
            else{
                wall[j][i][3]=p;
                hasWall[j][i]|=ok;
                ok=false;
            }
        }
    }
    queue<ii> q;
    q.emplace(s);
    memset(dis,-1,sizeof(dis));
    dis[s.first][s.second]=0;
    while (q.size()){
        ll x,y;
        tie(x,y)=q.front();
        q.pop();
        if (hasWall[x][y])
            for (int i=0;i<4;i++){
                ll nx=wall[x][y][i].first,ny=wall[x][y][i].second;
                if (dis[nx][ny]!=-1) continue;
                dis[nx][ny]=dis[x][y]+1;
                q.emplace(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]!=-1) continue;
            dis[nx][ny]=dis[x][y]+1;
            q.emplace(nx,ny);
        }
    }
    cout<<dis[e.first][e.second];
    return 0;
}

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