Cod sursa(job #2132754)

Utilizator dragos231456Neghina Dragos dragos231456 Data 16 februarie 2018 00:06:32
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#define h i1+i
#define o j1+j
#define k q[cost][0].i
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
struct cr{
    int i,j;
}dir[10],aux,q[5][250005];
int n,m,i1,j1,i2,j2,d,e,u[505][505],cost,b,l,c;
int a[505][505],inf(1<<30);
bool ok=true;

int directie(int i,int j)
{
    for(int r=1;r<=8;++r)
    {
        if(dir[r].i==i && dir[r].j==j) return r;
    }
}

void precalc()
{
    ///border
    for(int i=0;i<=n+1;++i) a[i][0]=a[i][m+1]=-1;
    for(int i=0;i<=m+1;++i) a[0][i]=a[n+1][i]=-1;

    ///directii \ | / 1 2 3
    ///         -   - 8   4
    ///         / | \ 7 6 5

    dir[1].i=dir[2].i=dir[3].i=-1; dir[1].j=-1; dir[3].j=1;
                                   dir[8].j=-1; dir[4].j=1;
    dir[6].i=dir[7].i=dir[5].i=1;  dir[7].j=-1; dir[5].j=1;

    ///primele numere in coada

    l=i1; c=j1;
    a[i1][j1]=0;
    aux.i=i1; aux.j=j1;
    q[0][0].i=1;
    q[0][1]=aux;
}

int main()
{
    f>>n>>m;
    f>>i1>>j1>>i2>>j2;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            f>>a[i][j];
            if(a[i][j]==1) a[i][j]=-1;
            else a[i][j]=inf;
        }
    }
    precalc();
    aux=q[0][1]; b=0;

    while(ok==true)
    {
        ok=false; cost=0;
        while(b==k)
        {
            cost=1;
            while(cost<=4)
            {
                for(int i=0;i<=k;++i)
                {
                    q[cost-1][i]=q[cost][i];
                }
                ++cost;
            }
            b=0;
            cost=0;
        }
        ++b;
        aux=q[0][b]; i1=aux.i; j1=aux.j;

        //cout<<i1<<' '<<j1<<endl;

        for(int i=-1;i<=1;++i)
        {
            for(int j=-1;j<=1;++j)
            {

                d=directie(i,j); e=u[i1][j1];
                cost=d-e; if(cost<0) cost=-cost;
                if(cost>4) cost=8-cost;
                if(l==i1 && c==j1) cost=0;


                if(a[h][o]>cost+a[i1][j1])
                {
                    u[h][o]=d;
                    a[h][o]=cost+a[i1][j1];
                    aux.i=h; aux.j=o; q[cost][++k]=aux;
                    ok=true;
                }
            }
        }
    }

    g<<a[i2][j2];
    return 0;
}