Submission #675238

#	Time	Username	Problem	Language	Result	Execution time	Memory
675238		vjudge1	Portals (BOI14_portals)	C++17	100 / 100	318 ms	42008 KiB

portals

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

const int maxN = 1001;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int r,c;
#define fi first
#define se second
string s[maxN];
ll d[maxN][maxN];
bool vis[maxN][maxN];
#define pli pair<int,int>
#define plii pair<ll,pli>
pli ed;
pli nxt[4][maxN][maxN];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> r >> c;
    priority_queue<plii,vector<plii>,greater<plii>>pq;
    for(int i=0;i<r;i++)
    {
        cin >> s[i];
        for(int j=0;j<c;j++)
        {
            d[i][j]=r*c+10;
            vis[i][j]=false;
            if(s[i][j]=='S')
            {
                pq.push({0,{i,j}});
                d[i][j]=0;
            }
            else if(s[i][j]=='C')
            {
                ed={i,j};
            }
        }
    }
    for(int i=0;i<r;i++)
    {
        int l=0;
        for(int j=0;j<c;j++)
        {
            nxt[0][i][j]={i,l};
            if(s[i][j]=='#') l=j+1;
        }
        l=c-1;
        for(int j=c-1;j>=0;j--)
        {
            nxt[1][i][j]={i,l};
            if(s[i][j]=='#') l=j-1;
        }
    }
    for(int j=0;j<c;j++)
    {
        int u=0;
        for(int i=0;i<r;i++)
        {
            nxt[2][i][j]={u,j};
            if(s[i][j]=='#') u=i+1;
        }
        u=r-1;
        for(int i=r-1;i>=0;i--)
        {
            nxt[3][i][j]={u,j};
            if(s[i][j]=='#') u=i-1;
        }
    }
    while(!pq.empty())
    {
        auto v=pq.top();
        pq.pop();
        int x=v.se.fi;
        int y=v.se.se;
        if(vis[x][y]) continue;
        if(s[x][y]=='#') continue;
        vis[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if(newx<0||newy<0||newx>=r||newy>=c) continue;
            if(s[newx][newy]!='#') if(d[newx][newy]>d[x][y]+1) d[newx][newy]=min(d[newx][newy],d[x][y]+1),pq.push({d[newx][newy],{newx,newy}});
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(i==j) continue;
                int w=abs(nxt[j][x][y].fi-x)+abs(nxt[j][x][y].se-y)+1;
                int newx=nxt[i][x][y].fi;
                int newy=nxt[i][x][y].se;
                if(d[newx][newy]>d[x][y]+w)
                {
                    d[newx][newy]=d[x][y]+w;
                    pq.push({d[newx][newy],{newx,newy}});
                }
            }
        }
    }
    cout << d[ed.fi][ed.se];
}

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