Submission #103945

#	Time	Username	Problem	Language	Result	Execution time	Memory
103945		Bodo171	Golf (JOI17_golf)	C++14	10 / 100	314 ms	84076 KiB

golf

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int kmax=100005;
const int nmax=2010;
struct state
{
    int l,c,dir;
};
vector<state> L[4*nmax];
int X1[kmax],X2[nmax],Y1[kmax],Y2[kmax];
int v[nmax][nmax];
int d[nmax][nmax][4];
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
int n,k,i,j,dir,l1,c1,l2,c2,li,ci,di,lf,cf,df;
void prp(int l,int c,int dd,int cost_nou)
{
    if(l<1||c<1||l>n||c>n) return;
    if(cost_nou<d[l][c][dd])
    {
        d[l][c][dd]=cost_nou;
        L[cost_nou].push_back({l,c,dd});
    }
}
void bfs()
{
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           for(dir=0;dir<4;dir++)
                d[i][j][dir]=(1<<30);
    for(int i=0;i<4;i++)
    {
        L[1].push_back({l1,c1,i});
        d[l1][c1][i]=1;
    }
    for(int cost=0;cost<=4*n;cost++)
    {
        for(int it=0;it<L[cost].size();it++)
        {
            li=L[cost][it].l;ci=L[cost][it].c;di=L[cost][it].dir;
            if(cost==d[li][ci][di])
            {
                for(df=0;df<4;df++)
                {
                    lf=li+d1[df];cf=ci+d2[df];
                    if(!((1<<df)&v[li][ci]))
                    {
                        prp(lf,cf,df,cost+(di!=df));
                    }
                }
            }
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>l1>>c1>>l2>>c2;
    l1++,c1++,l2++,c2++;
    n=max(l1+1,l2+1);
    n=max(n,max(c1+1,c2+1));
    cin>>k;
    for(i=1;i<=k;i++)
    {
        cin>>X1[i]>>X2[i]>>Y1[i]>>Y2[i];
        X1[i]++;Y1[i]++;X2[i]++;Y2[i]++;
        n=max(n,max(X1[i]+1,X2[i]+1));
        n=max(n,max(Y1[i]+1,Y2[i]+1));
    }
    for(i=1;i<=k;i++)
    {
        for(j=Y1[i]+1;j<=Y2[i]-1;j++)
        {
            v[X1[i]][j]|=4;
            v[X2[i]][j]|=1;
        }
        for(j=X1[i]+1;j<=X2[i]-1;j++)
        {
            v[j][Y1[i]]|=8;
            v[j][Y2[i]]|=2;
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(l1==i&&c1==j) cout<<"s ";
            else if(l2==i&&c2==j) cout<<"e ";
            else cout<<v[i][j]<<' ';
        }
        cout<<'\n';
    }*/
    bfs();
    int ans=(1<<30);
    for(int i=0;i<4;i++)
        ans=min(ans,d[l2][c2][i]);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

golf.cpp: In function 'void bfs()':
golf.cpp:40:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int it=0;it<L[cost].size();it++)
                      ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70