Submission #755776

#	Time	Username	Problem	Language	Result	Execution time	Memory
755776		DavidAA007	Portal (COCI17_portal)	C++14	0 / 120	35 ms	21068 KiB

portal

#include<bits/stdc++.h>
#define mare 1e9
#define mod 1000000007
#define bit(x,i)(((x)>>(i))&1)
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int T,n,m,ok,x,y,i,j;
int c,aux,start,maxx,summax,minn;
int s,dr,mij,contor,suma,poz;
char v[505][505];
vector<vector<int>> ans(n,vector<int>(m,2e9));
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
pair<int, int> inc,sfa,dp[505][505][5];
int main()
{
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>v[i][j];
            //cout<<v[i][j];
            if(v[i][j]=='C')
                inc={i,j};
            if(v[i][j]=='F')
                sfa={i,j};
        }
        //cout<<"\n";
    }
    for(i=0;i<n;i++)
    {
        aux=-1;
        for(j=0;j<m;j++)
        {
            if(v[i][j]=='#')
                aux=j;
            dp[i][j][0]={i,aux+1};
        }
    }
    for(i=0;i<n;i++)
    {
        aux=m;
        for(j=m-1;j>=0;j--)
        {
            if(v[i][j]=='#')
                aux=j;
            dp[i][j][1]={i,aux-1};
        }
    }
    for(j=0;j<m;j++)
    {
        aux=-1;
        for(i=0;i<n;i++)
        {
            if(v[i][j]=='#')
                aux=i;
            dp[i][j][2]={aux+1,j};
        }
    }
    for(j=0;j<m;j++)
    {
        aux=n;
        for(i=n-1;i>=0;i--)
        {
            if(v[i][j]=='#')
                aux=i;
            dp[i][j][3]={aux-1,j};
        }
    }
    //cout<<"ajung aci\n";
    auto distanta=[&](pair<int, int> f,pair<int, int> s)
    {
        return abs(f.first-s.first)+abs(f.second-s.second);
    };
    auto upd=[&](pair<int, int> f,int rez){
        if(ans[f.first][f.second]>rez){
            ans[f.first][f.second]=rez;
            q.push({rez,f});
        }
    };
    //cout<<"ajung aci\n";
    q.push({0,inc});
    ans[inc.first][inc.second]=0;
    while(!q.empty())
    {
       // cout<<"intru \n";
        auto c=q.top().second;
        auto dist=q.top().first;
        q.pop();
        if(ans[c.first][c.second]<dist)
            continue;
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                if(i==j)//diagonale
                    continue;
                pair<int, int> f=dp[c.first][c.second][i];
                pair<int, int> s=dp[c.first][c.second][j];
                int dist1=distanta(c,s)+dist+1;
                int dist2=distanta(c,f)+dist+1;
                upd(f,dist1);
                upd(s,dist2);
            }
        }
        //cout<<"ajung aci din nou\n";
        for(i=0;i<4;i++)
        {
            int ax=c.first+dx[i];
            int ay=c.second+dy[i];
            if(0<=ax && ax<n && 0<=ay && ay<m && v[ax][ay]!='#')
            {
                if(ans[ax][ay]>dist+1)
                {
                    ans[ax][ay]=dist+1;
                    q.push({dist+1,{ax,ay}});
                }
            }
        }
    }
    if(ans[sfa.first][sfa.second]==2e9)
    {
        cout<<"nemoguce";
    }
    else
    {
        cout<<ans[sfa.first][sfa.second];
    }
    return 0;
}
/*

4 4
####
#.F#
#C.#
####

*/

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12