Cod sursa(job #1792069)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 29 octombrie 2016 23:33:17
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <fstream>
#include <queue>
#include <climits>
#include <algorithm>
#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;
            q.push(t);
        }
    }
    while (!q.empty())
    {
        p=q.front();q.pop();
        if (p.x!=f.x || p.y!=f.y)
        {
            //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);
                }
            //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);
                    }

                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);
                    }
            }
            //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);
                }
        }
    }
}
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;
}