Submission #290634

#	Time	Username	Problem	Language	Result	Execution time	Memory
290634		Dymo	Portals (BOI14_portals)	C++14	100 / 100	529 ms	96684 KiB

portals

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define all(n) n.begin(),n.end()
#define endl "\n"
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
const ll maxn=2e3+500;
const ll mod=1e9+7 ;
const ll base=500;
/// con 9 ngay

ll d[maxn][maxn];
ll u[maxn][maxn];
ll r[maxn][maxn];
ll l[maxn][maxn];
ll d1[maxn][maxn];
ll dp[maxn][maxn];
char a[maxn][maxn];
ll ax[maxn]={1,0,-1,0};
ll ay[maxn]= {0,1,0,-1};
pll st;
pll ed;
ll n, m;
bool chk(ll i,ll j )
{
    if (i<1||i>n) return false;
    if (j<1||j>m) return false;
    if (a[i][j]=='#') return false;

    return true;

}
queue<pll> q;

void bfs()
{
    while (!q.empty())
    {
        auto p= q.front();
        q.pop();
        ll x=p.ff;
        ll  y= p.ss;
        for (int i=0;i<4;i++)
        {
            ll x1= x+ax[i];
            ll y1= y+ay[i];
            if (chk(x1,y1)&&d1[x1][y1]==1e15)
            {
                d1[x1][y1]=d1[x][y]+1;
                q.push(make_pair(x1,y1));
            }
        }
    }
}
void dosth()
{
    priority_queue<pair<ll,pll>, vector<pair<ll,pll>>, greater<pair<ll,pll>>> q;
    dp[st.ff][st.ss]=0;
   // cout <<st.ff<<" "<<st.ss<<endl;
    q.push(make_pair(dp[st.ff][st.ss],st));
    while (!q.empty())
    {
        auto p= q.top();
        q.pop();
        if (dp[p.ss.ff][p.ss.ss]!=p.ff) continue;

        ll x=p.ss.ff;
        ll y=p.ss.ss;
      //  cout <<x<<" "<<y<<" "<<dp[x][y]<<endl;
        for (int i=0;i<4;i++)
        {
            ll x1=x+ax[i];
            ll y1=y+ay[i];
            if (chk(x1,y1))
            {
                if (dp[x1][y1]>p.ff+1)
                {
                    dp[x1][y1]=p.ff+1;
                    q.push(make_pair(dp[x1][y1],make_pair(x1,y1)));
                }
            }
        }
        if (dp[l[x][y]][y]>dp[x][y]+d1[x][y]+1)
        {
           dp[l[x][y]][y]=dp[x][y]+d1[x][y]+1;
            q.push(make_pair(dp[l[x][y]][y],make_pair(l[x][y],y)));
        }
         if (dp[r[x][y]][y]>dp[x][y]+d1[x][y]+1)
        {
           dp[r[x][y]][y]=dp[x][y]+d1[x][y]+1;
            q.push(make_pair(dp[r[x][y]][y],make_pair(r[x][y],y)));
        }
        if (dp[x][u[x][y]]>dp[x][y]+d1[x][y]+1)
        {
           dp[x][u[x][y]]=dp[x][y]+d1[x][y]+1;
            q.push(make_pair(dp[x][u[x][y]],make_pair(x,u[x][y])));
        }
        if (dp[x][d[x][y]]>dp[x][y]+d1[x][y]+1)
        {
           dp[x][d[x][y]]=dp[x][y]+d1[x][y]+1;
            q.push(make_pair(dp[x][d[x][y]],make_pair(x,d[x][y])));
        }

    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.txt","r",stdin);
    if (fopen("Farm.INP","r"))
    {
        freopen("Farm.INP","r",stdin);
        freopen("Farm.OUT","w",stdout);
    }

    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
         cin>>a[i][j];
         d1[i][j]=1e15;
         dp[i][j]=1e15;
         if (a[i][j]=='S')
         {
             st=make_pair(i,j);
         }
         if (a[i][j]=='C')
         {
             ed=make_pair(i,j);

         }
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
           if (a[i][j]=='#')
           {
               for (int k=0;k<4;k++)
               {
                  ll x1=ax[k]+i;
                  ll y1=ay[k]+j;
                  if (chk(x1,y1))
                  {
                      d1[x1][y1]=0;
                      q.push(make_pair(x1,y1));
                  }
               }
           }
           else
           {
               if (i==1||i==n||j==1||j==m)
               {
                   d1[i][j]=0;
                   q.push(make_pair(i,j));

               }
           }
        }
    }
    bfs();
    for (int i=1;i<=n;i++)
    {
        ll pre=1;
        for (int j=1;j<=m;j++)
        {
            if (a[i][j]=='#') pre=j+1;
            else
            {
                u[i][j]=pre;
            }
        }
        pre=m;
        for (int j=m;j>=1;j--)
        {
            if (a[i][j]=='#') pre=j-1;
            else
            {
                d[i][j]=pre;
            }
        }
    }
    for (int j=1;j<=m;j++)
    {
        ll pre=1;
        for (int i=1;i<=n;i++)
        {
            if (a[i][j]=='#') pre=i+1;
            else
            {
                l[i][j]=pre;
            }
        }
        pre=n;
        for (int i=n;i>=1;i--)
        {
            if (a[i][j]=='#') pre=i-1;
            else
            {
                r[i][j]=pre;
            }
        }
    }
   /* for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            cout <<l[i][j]<<" "<<r[i][j]<<" "<<u[i][j]<<" "<<d[i][j]<<" "<<d1[i][j]<<endl;
        }
    }*/
    dosth();
   // cout <<ed.ff<<" "<<ed.ss<<endl;
    cout <<dp[ed.ff][ed.ss]<<endl;







}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  118 |         freopen("Farm.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
portals.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  119 |         freopen("Farm.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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