Cod sursa(job #1792009)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 29 octombrie 2016 22:21:38
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.69 kb
#include <fstream>
#include <queue>
#include <climits>
#define nmax 505
using namespace std;
unsigned int n,m;
bool P[nmax][nmax];
unsigned int D[nmax][nmax];
struct el {unsigned int x,y;};
el dep[8];
unsigned int r8(int x)
{
    x%=8;
    if (x<0) x+=8;
    return x;
}
struct pc{unsigned int cost,dir,x,y;};
queue <pc> q;
void bfs(el s, el f)
{
    D[s.x][s.y]=0;
    pc t,p;unsigned int i;
    t.cost=0;
    for (i=0;i<=7;i++)
    {
        t.x=s.x+dep[i].x;
        t.y=s.y+dep[i].y;
        if (!P[t.x][t.y])
        {
            t.dir=i;
            D[t.x][t.y]=0;
            q.push(t);
        }
    }
    while (!q.empty())
    {
        p=q.front();q.pop();
        //pastrarea directiei - 0
        t=p;
        t.x+=dep[t.dir].x;
        t.y+=dep[t.dir].y;
        if ((!P[t.x][t.y]))
        {
            if (D[t.x][t.y]>t.cost)
                {
                    D[t.x][t.y]=t.cost;
                    q.push(t);
                }
        }
        else
        {
            if (t.x==f.x && t.y==f.y)
            {
                if (D[t.x][t.y]>t.cost) D[t.x][t.y]=t.cost;
            }
        }
        //schimbarea directiei - 1,2,3
        for (i=1;i<=3;i++)
        {
            t.dir=r8(p.dir+i);
            t.cost=p.cost+i;
            t.x=p.x+dep[t.dir].x;
            t.y=p.y+dep[t.dir].y;
            if ((!P[t.x][t.y]))
            {
                if (D[t.x][t.y]>t.cost)
                {
                    D[t.x][t.y]=t.cost;
                    q.push(t);
                }
            }
            else
                {
                    if (t.x==f.x && t.y==f.y)
                    {
                        if (D[t.x][t.y]>t.cost) D[t.x][t.y]=t.cost;
                    }
                }
            t.dir=r8(p.dir-i);
            t.cost=p.cost+i;
            t.x=p.x+dep[t.dir].x;
            t.y=p.y+dep[t.dir].y;
            if ((!P[t.x][t.y]))
            {
                if (D[t.x][t.y]>t.cost)
                {
                    D[t.x][t.y]=t.cost;
                    q.push(t);
                }
            }
            else
                {
                    if (t.x==f.x && t.y==f.y)
                    {
                        if (D[t.x][t.y]>t.cost) D[t.x][t.y]=t.cost;
                    }
                }
        }
        //schimbarea sensului - 4
        t=p;
        t.dir=r8(t.dir+4);
        t.cost+=4;
        t.x+=dep[t.dir].x;
        t.y+=dep[t.dir].y;
        if (!P[t.x][t.y])
        {
            if (D[t.x][t.y]>t.cost)
                {
                    D[t.x][t.y]=t.cost;
                    q.push(t);
                }
        }
        else
                {
                    if (t.x==f.x && t.y==f.y)
                    {
                        if (D[t.x][t.y]>t.cost) D[t.x][t.y]=t.cost;
                    }
                }
    }
}
int main()
{
    ifstream f("car.in");
    ofstream g("car.out");
    unsigned int i,j;
    el s,fin;
    f>>n>>m>>s.x>>s.y>>fin.x>>fin.y;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            f>>P[i][j],D[i][j]=INT_MAX;
    for (i=0;i<=n;i++) P[i][0]=1;
    for (i=0;i<=m;i++) P[n+1][i]=1;
    for (i=n+1;i>=1;i--) P[i][m+1]=1;
    for (i=m+1;i>=1;i--) P[0][i]=1;
    {
        dep[0].x=-1;dep[0].y=0;
        dep[1].x=-1;dep[1].y=1;
        dep[2].x=0;dep[2].y=1;
        dep[3].x=1;dep[3].y=1;
        dep[4].x=1;dep[4].y=0;
        dep[5].x=1;dep[5].y=-1;
        dep[6].x=0;dep[6].y=-1;
        dep[7].x=-1;dep[7].y=-1;
    }
    bfs(s,fin);
    if (D[fin.x][fin.y]==INT_MAX) g<<"-1\n";
    else g<<D[fin.x][fin.y]<<'\n';
    f.close();
    g.close();
    return 0;
}