Cod sursa(job #1060302)

Utilizator japjappedulapPotra Vlad japjappedulap Data 17 decembrie 2013 20:57:43
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define DIM 502
#define INF 99999
ifstream is ("car.in");
ofstream os ("car.out");

struct Cel{int i, j;} Start, Finish;

queue <Cel> Q;

const int di[] = {-1,-1,0,1,1,1,0,-1};
const int dj[] = {0,1,1,1,0,-1,-1,-1};

bool a[DIM][DIM];
int D[DIM][DIM];
int Cost[DIM][DIM];
int n, m;

void Read();
void BFS();
void Solve();
bool Ok(int i, int j);
int SetPrice(int i, int j, int x);
int MOD(int x, int y);
void DEBUG();

int main()
{
    Read();
    BFS();
    Solve();
    //DEBUG();
    is.close();
    os.close();
    return 0;
}

void Solve()
{
    if (D[Finish.i][Finish.j] == 0)
    {
        os << -1;
        return;
    }
    os << Cost[Finish.i][Finish.j];
};

void Read()
{
    is >> n >> m;
    is >> Start.i >> Start.j >> Finish.i >> Finish.j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            is >> a[i][j];
};

void BFS()
{
    Cel Ac;
    int i, j, iv, jv;
    Q.push(Start);
    D[Start.i][Start.j] = 1;
    while (!Q.empty())
    {
        Ac = Q.front(), Q.pop();
        i = Ac.i, j = Ac.j;
        for (int dir = 0; dir < 8; dir++)
        {
            iv = i + di[dir];
            jv = j + dj[dir];
            if (Ok(iv, jv) && D[iv][jv] == 0 && a[iv][jv] == 0)
            {
                D[iv][jv] = D[i][j]+1;
                Ac.i = iv, Ac.j = jv;
                Q.push(Ac);
            }
            if (D[i][j] >= 3)
                Cost[i][j] = SetPrice(i, j, D[i][j]);
        }
    }
};

int SetPrice(int i, int j, int x)
{
    int iv, jv, in, jn;
    int rev = INF, mod;
    for (int dir1 = 0; dir1 < 8; ++dir1)
    {
        iv = i + di[dir1];
        jv = j + dj[dir1];
        if (D[iv][jv] == x-1 && Ok(iv, jv))
            for (int dir2 = 0; dir2 < 8; ++dir2)
            {
                in = iv + di[dir2];
                jn = jv + dj[dir2];
                if (D[in][jn] == x-2 && Ok(in, jn))
                {
                    mod = MOD(dir1, dir2);
                    mod += Cost[iv][jv];
                    rev = min(rev, mod);
                }
            }
    }
    return rev;
};

int MOD(int x, int y)
{
    if (x == y-4 || x-4 == y)
        return 0;
    if (x == y-3 || x-3 == y || x-5 == y || x == y-5)
        return 1;
    if (x == y-2 || x-2 == y || x-6 == y || x == y-6)
        return 2;
    if (x == y-1 || x-1 == y || x-7 == y || x == y-7)
        return 3;
    return 0;
};

bool Ok(int i, int j)
{
    if (i < 1 || j < 1 || i > n || j > m) return false;
    return true;
};

void DEBUG()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            os << Cost[i][j] << ' ';
        os << '\n';
    }
    os << '\n';
};