Submission #941136

#	Time	Username	Problem	Language	Result	Execution time	Memory
941136		Faisal_Saqib	Portals (BOI14_portals)	C++17	100 / 100	208 ms	23444 KiB

portals

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char grid[N][N];
bool vis[N][N];
int n,m;
vector<pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
bool valid(int i,int j)
{
    if(min(i,j)>=0 and i<n and j<m and grid[i][j]!='#')
        return 1;
    return 0;
}
int dist[N][N],before[N][N],after[N][N],up[N][N],down[N][N];
void dp(int sx,int sy)
{
  dist[sx][sy]=0;
  priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
  pq.push({0,{sx,sy}});
  while(pq.size())
  {
    auto tp=pq.top();
    pq.pop();
    int dip=tp.first;
    pair<int,int> pt=tp.second;
    if(dist[pt.first][pt.second]==dip)
    {
        // cout<<"Hola "<<pt.first<<' '<<pt.second<<' '<<dip<<endl;
        vis[pt.first][pt.second]=1;
        for(int j=0;j<4;j++)
        {
            if(valid(pt.first+dir[j].first,pt.second+dir[j].second) and dist[pt.first+dir[j].first][pt.second+dir[j].second]>dip+1)
            {
                dist[pt.first+dir[j].first][pt.second+dir[j].second]=dip+1;
                pq.push({dip+1,{pt.first+dir[j].first,pt.second+dir[j].second}});
            }
        }
        // Go to Up first
        {
            // Up
            int j=up[pt.first][pt.second];
            int jp=down[pt.first][pt.second];
            int curd=dip+(pt.first-j);
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }
 
            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }
 
            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }
 
        {
            // Down
            int j=down[pt.first][pt.second];
            int jp=up[pt.first][pt.second];
            int curd=dip+(j-pt.first);
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }
 
            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }
 
            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }
 
        {
            // Down
            int j=before[pt.first][pt.second];
            int curd=dip+(pt.second-j);
            int jp=up[pt.first][pt.second];
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }
 
            jp=down[pt.first][pt.second];
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }
 
            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }
 
        {
            // Down
            int j=after[pt.first][pt.second];
            int curd=dip+(j-pt.second);
            int jp=up[pt.first][pt.second];
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }
 
            jp=down[pt.first][pt.second];
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }
 
            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }
        }
    }
  }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    n+=2;
    m+=2;
    int sx=0,sy=0,cx,cy;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i==0 or j==0 or i==n-1 or j==m-1)
            {
                grid[i][j]='#';
            }
            else{
                cin>>grid[i][j];
                if(grid[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
                if(grid[i][j]=='C')
                {
                    cx=i;
                    cy=j;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dist[i][j]=1e9;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]=='#')
            {
                before[i][j]=j;
            }
            else{
                before[i][j]=before[i][j-1];
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(grid[i][j]=='#')
            {
                after[i][j]=j;
            }
            else{
                after[i][j]=after[i][j+1];
            }
        }
    }
    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            if(grid[i][j]=='#')
            {
                up[i][j]=i;
            }
            else{
                up[i][j]=up[i-1][j];
            }
        }
    }
    for(int j=0;j<m;j++)
    {
        for(int i=n-1;i>=0;i--)
        {
            if(grid[i][j]=='#')
            {
                down[i][j]=i;
            }
            else{
                down[i][j]=down[i+1][j];
            }
        }
    }
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<m;j++)
    //     {
    //         cout<<grid[i][j];
    //     }
    //     cout<<endl;;
    // }  
    dp(sx,sy);
    cout<<dist[cx][cy];
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:245:22: warning: 'cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  245 |     cout<<dist[cx][cy];
      |                      ^
portals.cpp:245:22: warning: 'cx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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