Submission #675192

#	Time	Username	Problem	Language	Result	Execution time	Memory
675192		vjudge1	Portals (BOI14_portals)	C++17	0 / 100	4 ms	8608 KiB

portals

#include<bits/stdc++.h>

using namespace std;
#define N  1010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define ld long double
#define iiii   pair<pair<ld,int>,ii>

int ktr[N][N],l[N][N],r[N][N],up[N][N],kq[N][N],down[N][N],nxt[N][N],ans=1e9,n,m,dp[N][N][3];
vector<int>h={0,0,-1,1},c={-1,1,0,0};
string a[N];
queue<ii>s;
priority_queue<iii>dq;

bool check(int u,int v)
{
    return(u>=1&&u<=n&&v>=1&&v<=m&&a[u][v]!='#');
}

void BFS(int id)
{
    while(!s.empty())
    {
        ii cc=s.front();
        s.pop();
        int u=cc.fs,v=cc.sc;
       // cout<<u<<" "<<v<<" "<<dp[u][v][id]<<endl;
        for(int i=0;i<4;i++)
            if(check(u+h[i],v+c[i])&&dp[u+h[i]][v+c[i]][id]>dp[u][v][id]+1)
            {
                dp[u+h[i]][v+c[i]][id]=dp[u][v][id]+1;
                s.push({u+h[i],v+c[i]});
            }
    }
}

int main()
{
  //  freopen("A.inp","r",stdin);
  //  freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],a[i]=' '+a[i];
  //  memset(dp,0x3f3f,sizeof(dp));
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++)
            for(int id=0;id<=2;id++)
                dp[i][j][id]=1e8;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='#')
            {
                dp[i][j][2]=0;
                s.push({i,j});
            }
    for(int i=1;i<=n;i++)
    {
        dp[i][0][2]=0;
        s.push({i,0});
        dp[i][m+1][2]=0;
        s.push({i,m+1});
    }
    for(int i=1;i<=m;i++)
    {
        dp[0][i][2]=0;
        s.push({0,i});
        dp[n+1][i][2]=0;
        s.push({n+1,i});
    }
    BFS(2);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='S')
            {
                dp[i][j][0]=0;
                s.push({i,j});
            }
    BFS(0);
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='C')
            {
                dp[i][j][1]=0;
                s.push({i,j});
            }
    BFS(1);
    //cout<<dp[1][1][0];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=min(ans,dp[i][j][0]+dp[i][j][1]);
    memset(nxt,-1,sizeof(nxt));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='#')
                nxt[i][j]=j;
                    else nxt[i][j]=nxt[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]!='#'&&nxt[i][j]==-1)
            {
                ans=min(ans,dp[i][j][0]+dp[i][j][2]+dp[i][1][1]);
            }
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++)
        {
            l[i][j]=1;
            up[i][j]=1;
            r[i][j]=m;
            down[i][j]=n;
        }
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='#')
            {
                l[i][j]=i+1;
                up[i][j]=j+1;
            }else
            {
                l[i][j]=l[i-1][j];
                up[i][j]=up[i][j-1];
            }
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
            if(a[i][j]=='#')
            {
                r[i][j]=i-1;
                down[i][j]=j-1;
            }else
            {
                r[i][j]=r[i+1][j];
                down[i][j]=down[i][j+1];
            }
    memset(kq,0x3f3f,sizeof(kq));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='S')
            {
                kq[i][j]=0;
                dq.push({0,{i,j}});
            }
    while(!dq.empty())
    {
        iii cc=dq.top();
        int u=cc.sc.fs,v=cc.sc.sc;
        dq.pop();
        if(ktr[u][v])
            continue;
        ktr[u][v]=1;
        if(a[u][v]=='C')
        {
            cout<<kq[u][v];
            return 0;
        }
      //  cout<<u<<" "<<v<<" "<<kq[u][v]<<endl;
        for(int i=1;i<=4;i++)
            if(check(u+h[i],v+c[i])&&kq[u+h[i]][v+c[i]]>kq[u][v]+1)
            {
                kq[u+h[i]][v+c[i]]=kq[u][v]+1;
                dq.push({-kq[u+h[i]][v+c[i]],{u+h[i],v+c[i]}});
            }
        if(kq[l[u][v]][v]>kq[u][v]+dp[u][v][2])
        {
            kq[l[u][v]][v]=kq[u][v]+dp[u][v][2];
            dq.push({-kq[l[u][v]][v],{l[u][v],v}});
        }

         if(kq[r[u][v]][v]>kq[u][v]+dp[u][v][2])
        {
            kq[r[u][v]][v]=kq[u][v]+dp[u][v][2];
            dq.push({-kq[r[u][v]][v],{r[u][v],v}});
        }

         if(kq[u][up[u][v]]>kq[u][v]+dp[u][v][2])
        {
            kq[u][up[u][v]]=kq[u][v]+dp[u][v][2];
            dq.push({-kq[u][up[u][v]],{u,up[u][v]}});
        }

        if(kq[u][down[u][v]]>kq[u][v]+dp[u][v][2])
        {
            kq[u][down[u][v]]=kq[u][v]+dp[u][v][2];
            dq.push({-kq[u][down[u][v]],{u,down[u][v]}});
        }
    }
    cout<<ans;
    return 0;
}

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