Cod sursa(job #1256972)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 7 noiembrie 2014 01:41:40
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
//Roberto Deresu - FMI
//Re :)
#include<fstream>
#include<queue>
using namespace std;
int n,m,i,j,x,y,d,xi,yi,xf,yf,sol,a[505][505],b[10][505][505];
queue<int>q;

ifstream fin("car.in");
ofstream fout("car.out");

int val(int d1,int d2)
{
    if(d1 == 0)return 0;

    if(d1 < d2)d1 = d1^d2^(d2 = d1);

    if(d1-d2 == 4)return 4;

    if(d1-d2 == 3 || d1-d2 == 5)return 3;

    if(d1-d2 == 2 || d1-d2 == 6)return 2;

    if(d1-d2 == 1 || d1-d2 == 7)return 1;

    if(d1-d2 == 0)return 0;
}

void citire()
{
    fin>>n>>m;
    fin>>xi>>yi>>xf>>yf;

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j], a[i][j] = 1-a[i][j];
}

void re()
{
    q.push(xi);
    q.push(yi);
    q.push(0);

    b[0][xi][yi] = 1;
    sol = 0;

    while(!q.empty())
    {
        x = q.front(), q.pop();
        y = q.front(), q.pop();
        d = q.front(), q.pop();


        if(a[x+1][y] && (b[1][x+1][y] >= b[d][x][y] + val(d,1) || !b[1][x+1][y]))
        {
            b[1][x+1][y] = b[d][x][y] + val(d,1);

            q.push(x+1);
            q.push(y);
            q.push(1);
        }


        if(a[x+1][y+1] && (b[2][x+1][y+1] >= b[d][x][y] + val(d,2) || !b[2][x+1][y+1]))
        {
            b[2][x+1][y+1] = b[d][x][y] + val(d,2);

            q.push(x+1);
            q.push(y+1);
            q.push(2);
        }


        if(a[x][y+1] && (b[3][x][y+1] >= b[d][x][y] + val(d,3) || !b[3][x][y+1]))
        {
            b[3][x][y+1] = b[d][x][y] + val(d,3);

            q.push(x);
            q.push(y+1);
            q.push(3);
        }


        if(a[x-1][y+1] && (b[4][x-1][y+1] >= b[d][x][y] + val(d,4) || !b[4][x-1][y+1]))
        {
            b[4][x-1][y+1] = b[d][x][y] + val(d,4);

            q.push(x-1);
            q.push(y+1);
            q.push(4);
        }


        if(a[x-1][y] && (b[5][x-1][y] >= b[d][x][y] + val(d,5) || !b[5][x-1][y]))
        {
            b[5][x-1][y] = b[d][x][y] + val(d,5);

            q.push(x-1);
            q.push(y);
            q.push(5);
        }


        if(a[x-1][y-1] && (b[6][x-1][y-1] >= b[d][x][y] + val(d,6) || !b[6][x-1][y-1]))
        {
            b[6][x-1][y-1] = b[d][x][y] + val(d,6);

            q.push(x-1);
            q.push(y-1);
            q.push(6);
        }


        if(a[x][y-1] && (b[7][x][y-1] >= b[d][x][y] + val(d,7) || !b[7][x][y-1]))
        {
            b[7][x][y-1] = b[d][x][y] + val(d,7);

            q.push(x);
            q.push(y-1);
            q.push(7);
        }


        if(a[x+1][y-1] && (b[8][x+1][y-1] >= b[d][x][y] + val(d,8) || !b[8][x+1][y-1]))
        {
            b[8][x+1][y-1] = b[d][x][y] + val(d,8);

            q.push(x+1);
            q.push(y-1);
            q.push(8);
        }

    }
}

void afisare()
{

    for(i=0;i<=8;i++)
        if(b[i][xf][yf] && (b[i][xf][yf] < sol || !sol)) sol = b[i][xf][yf];

    fout<<sol-1;
}



int main()
{
    citire();

    re();

    afisare();

	return 0;
}