Cod sursa(job #1171461)

Utilizator lucian666Vasilut Lucian lucian666 Data 15 aprilie 2014 19:28:26
Problema Car Scor 50
Compilator cpp Status done
Runda ubb_acm_etapa_individuala1 Marime 2.05 kb


//Code by Vasilut
# include <fstream>
# include <iostream>
# include <queue>
# include <algorithm>
# define infinit 0x3f3f3f3f
# define DIM 505

using namespace std;
ofstream out("car.out");

int n, m, a[DIM][DIM], b[DIM][DIM], p[DIM][DIM], di[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dj[8]={0, 1, 1, 1, 0, -1, -1, -1};
int ist, jst, ifin, jfin, o[10][10], op[8]={4,5,6,7,0,1,2,3};

void read ()
{
    ifstream in ("car.in");
    in>>n>>m>>ist>>jst>>ifin>>jfin;//read the position

    for(int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            in>>a[i][j];
}

void init ()
{
    //stabilesc curbele ( 45 , 135 ... )
    for(int i=0;i<8;++i)
        for(int j=i;j<8;++j)
            if (j-i==4)o[i][j]=o[j][i]=0;
            else if ((j-i)%4==2)o[i][j]=o[j][i]=2;
            else if (j-i==5 || j-i==3)o[i][j]=o[j][i]=1;
            else if (i+1==j || (i==0 && j==7))o[i][j]=o[j][i]=3;
            else o[i][j]=o[j][i]=4;
}

int inline in_m (int i, int j)
{

    if (i && j && i<=n && j<=m)
        return 1;
    return 0;


}

void solve ()
{
    queue <int> Qi , Qj;

    Qi.push(ist);
    Qj.push(jst);

    p[ist][jst]=-1;

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            b[i][j]=infinit;

    b[ist][jst]=0;

    int i, j, ii, jj;

    while (Qi.size())
    {
        i=Qi.front();
        Qi.pop();

        j=Qj.front();
        Qj.pop();

        for(int k=0;k<8;++k)
        {
            ii=i+di[k];
            jj=j+dj[k];

            int c;
            if (p[i][j]==-1)
                c=0;
            else
            c=o[op[p[i][j]]][k];

            if (in_m (ii, jj) && !a[ii][jj] && b[i][j]+c<b[ii][jj])
            {
                b[ii][jj]=b[i][j]+c;
                p[ii][jj]=k;
                if (ii!=ifin || jj!=jfin)
                {
                    Qi.push(ii);
                    Qj.push(jj);
                }
            }
        }
    }
}

int main ()
{
    read ();
    init();
    solve ();

    out<<b[ifin][jfin];

    return 0;
}