Cod sursa(job #2132632)

Utilizator dragos231456Neghina Dragos dragos231456 Data 15 februarie 2018 22:16:21
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <queue>
#define h i1+i
#define o j1+j
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
struct cr{
    short i,j;
}dir[10],aux;
short n,m,i1,j1,i2,j2,d,e,u[505][505],mn,cost;
int a[505][505],inf(1<<30);
queue<cr>q[250005]; 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

    a[i1][j1]=0;
    for(int i=-1;i<=1;++i)
    {
        for(int j=-1;j<=1;++j)
        {
            d=directie(i,j);
            if(a[h][o]==inf)
            {
                aux.i=h; aux.j=o;
                q[0].push(aux);
                u[h][o]=d;
                a[h][o]=0;
            }
        }
    }

}

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].front();
    mn=0;

    while(ok==true)
    {
        ok=false;
        while(q[mn].empty()) ++mn;
        aux=q[mn].front(); i1=aux.i; j1=aux.j; q[mn].pop();

        //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(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[a[h][o]].push(aux);
                    ok=true;
                }
            }
        }
    }

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