Cod sursa(job #205627)

Utilizator savimSerban Andrei Stan savim Data 2 septembrie 2008 10:34:19
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.9 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxl 510
#define maxval 500010

int n,m,i,j,k,x1,y1,x2,y2,p,q,l;
int a[maxl][maxl],fol[maxl][maxl];
int o[4]={0,0,-1,1};
int v[4]={-1,1,0,0};
vector <int> sir[maxval],vine[maxval];

void drumpar(int l1, int c1, int l2, int c2, int l3, int c3, int x)
{
    //drumul este paralel cu Ox
    if (l1==l3)
    {
        //45 grade
        if ((i+1<fol[l3+1][c3] || fol[l3][c3]<0) && !a[l3+1][c3])
        {
            sir[i+1].push_back(l3*m+c3);
            vine[i+1].push_back(x);
            fol[l3+1][c3]=i+1;
        }
        if ((i+1<fol[l3-1][c3] || fol[l3-1][c3]<0) && !a[l3-1][c3])
        {
            sir[i+1].push_back((l3-2)*m+c3);
            vine[i+1].push_back(x);
            fol[l3-1][c3]=i+1;
        }

        //90 grade
        if ((i+2<fol[l3+1][c1] || fol[l3+1][c1]<0) && !a[l3+1][c1])
        {
            sir[i+2].push_back(l3*m+c1);
            vine[i+2].push_back(x);
            fol[l3+1][c1]=i+2;
        }
        if ((i+2<fol[l3-1][c1] || fol[l3-1][c1]<0) && !a[l3-1][c1])
        {
            sir[i+2].push_back((l3-2)*m+c1);
            vine[i+2].push_back(x);
            fol[l3-1][c1]=i+2;
        }        
    }
    else
    {
        //drumul este paralel cu Oy

        //45 grade
        if ((i+1<fol[l3][c3-1] || fol[l3][c3-1]) && !a[l3][c3-1])
        {
            sir[i+1].push_back((l3-1)*m+c3-1);
            vine[i+1].push_back(x);
            fol[l3][c3-1]=i+1;
        }
        if ((i+1<fol[l3][c3+1] || fol[l3][c3+1]) && !a[l3][c3+1])
        {
            sir[i+1].push_back((l3-1)*m+c3+1);
            vine[i+1].push_back(x);
            fol[l3][c3+1]=i+1;
        }

        //90 grade
        if ((i+2<fol[l3][c2-1] || fol[l3][c2-1]<0) && !a[l3][c2-1])
        {
            sir[i+2].push_back((l3-1)*m+c2-1);
            vine[i+2].push_back(x);
            fol[l3][c2-1]=i+2;
        }
        if ((i+2<fol[l3][c2+1] || fol[l3][c2+1]<0) && !a[l3][c2+1])
        {
            sir[i+2].push_back((l3-1)*m+c2+1);
            vine[i+2].push_back(x);
            fol[l3][c2+1]=i+2;
        }
    }

}
void expand(int x, int y)
{
    int l1,c1,l2,c2,l3,c3;

    l1=(x/m)+1;c1=x%m;
    if (c1==0) {c1=m;l1--;}

    l2=(y/m)+1;c2=y%m;
    if (c2==0) {c2=m;l2--;}

    //ma duc pe directia 0
    l3=l1-l2;c3=c1-c2;
    l3+=l1;c3+=c1;
    if ((i<fol[l3][c3] || fol[l3][c3]<0) && !a[l3][c3])
    {
        sir[i].push_back((l3-1)*m+c3);
        vine[i].push_back(x);
        fol[l3][c3]=i;
    }

    //daca drumul este paralel cu axele de coordonate
    if (l1==l3 || c1==c3)
    {
        drumpar(l1,c1,l2,c2,l3,c3,x);
        return;
    }

    //ma duc la 45 grade, stanga dreapta
    //(c2,l3) (l2,c3)
    if ((i+1<fol[l1][c3] || fol[l1][c3]<0) && !a[l1][c3])
    {
        sir[i+1].push_back((l1-1)*m+c3);
        vine[i+1].push_back(x);
        fol[l1][c3]=i+1;
    }
    if ((i+1<fol[l3][c1] || fol[l3][c1]<0) && !a[l3][c1])
    {
        sir[i+1].push_back((l3-1)*m+c1);
        vine[i+1].push_back(x);
        fol[l3][c1]=i+1;
    }

    //ma duc la 90 grade, stanga dreapta
    //(c1,l3) (l1,c3);
    if ((i+2<fol[l3][c2] || fol[l3][c2]<0) && !a[l3][c2])
    {
        sir[i+2].push_back((l3-1)*m+c2);
        vine[i+2].push_back(x);
        fol[l3][c2]=i+2;
    }
    if ((i+2<fol[l2][c3] || fol[l2][c3]<0) && !a[l2][c3])
    {
        sir[i+2].push_back((l2-1)*m+c3);
        vine[i+2].push_back(x);
        fol[l2][c3]=i+2;
    }

}

int solutie(int p)
{
    int x=(p/m)+1,y=p%m;
    if (y==0) {y=m;x--;}

    if (x==x2 && y==y2) return 1;
    else return 0;
}

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);

    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            scanf("%d ",&a[i][j]);
            fol[i][j]=-1;
        }
    //bordez matricea cu 1
    for (i=0; i<=m+1; i++)
    {
        a[0][i]=1;
        a[n+1][i]=1;
    }
    for (i=0; i<=n+1; i++)
    {
        a[i][0]=1;
        a[i][m+1]=1;
    }
    
    fol[x1][y1]=0;
    for (i=0; i<4; i++)
        for (j=0; j<4; j++)
        {
            p=x1+o[i];q=y1+v[j];
            if (p>0 && p<=n && q>0 && q<=m && !a[p][q] && fol[p][q]<0)
            {
                fol[p][q]=0;
                sir[0].push_back((p-1)*m+q);
                vine[0].push_back((p-o[i]-1)*m+q-v[j]);
            }
        }

    for (i=0; i<=maxval; i++)
    {
        while (sir[i].size()>0)
        {
            l=sir[i].size()-1;

            p=sir[i][l];sir[i].pop_back();
            q=vine[i][l];vine[i].pop_back();

            expand(p,q);

            if (solutie(p))
            {
                printf("%d\n",i);
                return 0;
            }
        }
    }

    printf("-1\n");
    return 0;
}