Submission #675205

#	Time	Username	Problem	Language	Result	Execution time	Memory
675205		vjudge1	Portals (BOI14_portals)	C++17	0 / 100	1 ms	488 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;
ll lft[maxN][maxN],rght[maxN][maxN],up[maxN][maxN],down[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++)
        {
            lft[i][j]=l;
            if(s[i][j]=='#') l=j+1;
        }
        l=c-1;
        for(int j=c-1;j>=0;j--)
        {
            rght[i][j]=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++)
        {
            up[i][j]=u;
            if(s[i][j]=='#') u=i+1;
        }
        u=r-1;
        for(int i=r-1;i>=0;i--)
        {
            down[i][j]=u;
            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;
        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]=='#')continue;
            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}});
        }
        if(x==0||s[x-1][y]=='#')
        {
            int newx=down[x][y];
            int newy=y;
            if(s[newx][newy]=='#') continue;
            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}});
        }
        if(y==0||s[x][y-1]=='#')
        {
            int newy=rght[x][y];
            int newx=x;
            if(s[newx][newy]=='#') continue;
            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}});
        }
        if(x==r-1||s[x+1][y]=='#')
        {
            int newx=up[x][y];
            int newy=y;
            if(s[newx][newy]=='#') continue;
            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}});
        }
        if(y==c-1||s[x][y+1]=='#')
        {
            int newy=lft[x][y];
            int newx=x;
            if(s[newx][newy]=='#') continue;
            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}});
        }
    }
    cout << d[ed.fi][ed.se];
}

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