Submission #940991

#	Time	Username	Problem	Language	Result	Execution time	Memory
940991		Muhammad_Aneeq	Portals (BOI14_portals)	C++17	100 / 100	415 ms	40528 KiB

portals

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int y[4]={0,0,1,-1},x[4]={1,-1,0,0};
int const N=1010;
char a[N][N]={};
int n,m;
int ans=1e9+10;
bool vis[N][N][8]={};
int dist[N][N]={};
pair<int,int>por[N][N][4]={};
int dis(pair<int,int>a,pair<int,int>b)
{
    return abs(a.first-b.first)+abs(b.second-a.second);
}
bool check(int i,int j,int dir)
{
    if (i<=0||i>n||j<=0||j>m||a[i][j]=='#')
        return 0;
    return 1;
}
void bfs(int i,int j)
{
    set<vector<int>>ind;
    ind.insert({0,i,j,-1});
    while (ind.size())
    {
        vector<int>z=*begin(ind);
        ind.erase(z);
        if (a[z[1]][z[2]]=='C')
            continue;
        for (int i=0;i<4;i++)
        {
            int f=1e9+10;
            for (int j=0;j<4;j++)
                f=min(f,dis({z[1],z[2]},por[z[1]][z[2]][j])+(i!=j));
            if (check(por[z[1]][z[2]][i].first,por[z[1]][z[2]][i].second,i+4)&&dist[por[z[1]][z[2]][i].first][por[z[1]][z[2]][i].second]>z[0]+f)
            {
                dist[por[z[1]][z[2]][i].first][por[z[1]][z[2]][i].second]=z[0]+f;
                ind.insert({z[0]+f,por[z[1]][z[2]][i].first,por[z[1]][z[2]][i].second,i+4});
            }
        }
        for (int i=0;i<4;i++)
        {
            if (check(z[1]+x[i],z[2]+y[i],i)&&dist[z[1]+x[i]][z[2]+y[i]]>z[0]+1)
            {
                dist[z[1]+x[i]][z[2]+y[i]]=z[0]+1;
                ind.insert({z[0]+1,z[1]+x[i],z[2]+y[i],i});
            }
        }
    }
}
inline void solve()
{
    cin>>n>>m;
    int sti=0,stj=0,eni=0,enj=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if (a[i][j]=='S')
                sti=i,stj=j;
            if (a[i][j]=='C')
                eni=i,enj=j;
            dist[i][j]=1e9+10;
        }
    for (int i=0;i<=n;i++)
    {
        a[i][0]='#';
        a[i][m+1]='#';
    }
    for (int i=0;i<=m;i++)
    {
        a[0][i]='#';
        a[n+1][i]='#';
    }
    for (int j=1;j<=m;j++)
        for (int i=1;i<=n;i++)
        {
            if (a[i][j]!='#')
            {
                int k=i;
                while (a[k][j]!='#')
                    k++;
                k--;
                for (int l=i;l<=k;+l++)
                {
                    por[l][j][0]={i,j};
                    por[l][j][1]={k,j};
                }
                i=k;
            }
        }
    for (int j=1;j<=n;j++)
    {
        for (int i=1;i<=m;i++)
        {
            if (a[j][i]!='#')
            {
                int k=i;
                while (a[j][k]!='#')
                    k++;
                k--;
                for (int l=i;l<=k;l++)
                {
                    por[j][l][2]={j,i};
                    por[j][l][3]={j,k};
                }
                i=k;
            }
        }
    }
    pair<int,int>f={1,5};
    dist[sti][stj]=0;
    bfs(sti,stj);
    cout<<dist[eni][enj]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Compilation message (stderr)

portals.cpp: In function 'void solve()':
portals.cpp:94:35: warning: value computed is not used [-Wunused-value]
   94 |                 for (int l=i;l<=k;+l++)
      |                                   ^~~~
portals.cpp:121:18: warning: variable 'f' set but not used [-Wunused-but-set-variable]
  121 |     pair<int,int>f={1,5};
      |                  ^

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