Cod sursa(job #1256293)

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

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

int val(int d1,int d2)
{
    int c = 0;

    if(!d1 || d1 == d2)return 0;

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

    if((d1-1)/4 != (d2-1)/4) d1 = 9-d1, c=1;

    if(d1>d2) return d1-d2+c;
    else return d2-d1+c;
}

void citire()
{
    fin>>n>>m;
    fin>>xi>>yi>>xf>>yf;
    fin.getline(s,sizeof(s));

    for(i=1;i<=n;i++)
    {
        fin.getline(s,sizeof(s));
        for(j=0;j<m;j++)
            a[i][j+1] = 1-(s[2*j]-'0');
    }
}


int main()
{
    citire();

    q.push(xi);
    q.push(yi);
    q.push(0);
    b[xi][yi]=1;

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

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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

    fout<<b[xf][yf]-1;

	return 0;
}