Cod sursa(job #1527731)

Utilizator costyv87Vlad Costin costyv87 Data 18 noiembrie 2015 17:46:45
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <cstdio>
#include <queue>
using namespace std;
FILE *f,*g;

int n,m;
int d[510][510][8];
int a[510][510];
int dx[8] = {-1,-1,-1,0,+1,+1,+1,0};
int dy[8] = {-1,0,+1,+1,+1,0,-1,-1};

struct point
{
    int x,y;
    point(){}
    point(int X,int Y):x(X),y(Y){}
    point operator+(int dir)
    {
        return point(dx[dir]+x, dy[dir]+y);
    }
};
struct stare
{
    point p;
    int dir;
    stare(){}
    stare(point P, int d):p(P),dir(d){}
    int operator-(stare other)
    {
        int mn = min(dir, other.dir);
        int mx = max(dir, other.dir);

        return min(mx-mn , 8-mx+mn);
    }
};
point st,dr;

bool ok(point p)
{
    if (p.x < 1 || p.x > n || p.y < 1 || p.y > m || a[p.x][p.y] == 1) return false;
    return true;
}


void solve()
{
    queue<stare> q;

    for (int i = 0;i < 8; i++)
    {
        d[st.x][st.y][i] = 1;
        q.push(stare(st,i));
    }

    while (q.size())
    {
        stare now = q.front();
        q.pop();
        bool ok2 = false;


        int dir1 = (now.dir + 1) %8;

        if (d[now.p.x][now.p.y][dir1] == 0 || d[now.p.x][now.p.y][dir1] > d[now.p.x][now.p.y][now.dir] + 1)
        {
            d[now.p.x][now.p.y][dir1] = d[now.p.x][now.p.y][now.dir] + 1;
            q.push(stare(now.p, dir1));
        }
        dir1 = (now.dir + 7) %8;
        if (d[now.p.x][now.p.y][dir1] == 0 || d[now.p.x][now.p.y][dir1] > d[now.p.x][now.p.y][now.dir] + 1)
        {
            d[now.p.x][now.p.y][dir1] = d[now.p.x][now.p.y][now.dir] + 1;
            q.push(stare(now.p, dir1));
        }

        for (int k = -1;k <= 1;k++)
        {
            int i = (now.dir + k + 8) % 8;
            if (ok(now.p + i))
            {
                ok2 = true;
                stare then = stare( now.p + i, i);
                int add_cost = now - then;
                if (d[then.p.x][then.p.y][i] == 0 || d[then.p.x][then.p.y][i] > d[now.p.x][now.p.y][now.dir] + add_cost)
                {
                    d[then.p.x][then.p.y][i] = d[now.p.x][now.p.y][now.dir] + add_cost;
                    q.push(then);
                }
            }
        }


    }

    int ans = 0;

    for (int i =0;i < 8;i++)
        if (d[dr.x][dr.y][i] > 0)
        {
            if (ans == 0 || ans > d[dr.x][dr.y][i])
                ans = d[dr.x][dr.y][i];
        }
    fprintf(g,"%d",ans-1);
}

int main()
{
    f = fopen("car.in","r");
    g = fopen("car.out","w");

    fscanf(f,"%d%d",&n,&m);
    fscanf(f,"%d%d%d%d",&st.x, &st.y, &dr.x, &dr.y);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            fscanf(f,"%d",&a[i][j]);

    solve();

    return 0;
}