Cod sursa(job #1328087)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 28 ianuarie 2015 00:10:29
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <queue>
#define Nmax 505
#define INF 2000000000

using namespace std;

struct cell
{
    int lin,col,dir,cost;
} start,stop;
queue <cell> Q1,Q2;

const int dx[]={-1,0,1,1, 1, 0,-1,-1};
const int dy[]={ 1,1,1,0,-1,-1,-1, 0};
int a[Nmax][Nmax],ans=INF,n,m,dp[Nmax][Nmax][10];

inline bool Ok(cell w)
{
    if(w.lin<1 || w.lin>n | w.col<1 || w.col>m || a[w.lin][w.col]) return false;
    return true;
}

inline void Dijkstra()
{
    cell w,w1;
    int t;
    w.cost=0;
    for(t=0;t<=7;++t)
    {
        w.lin=start.lin+dx[t]; w.col=start.col+dy[t]; w.dir=t;
        if(!Ok(w)) continue;
        Q1.push(w);
    }
    while(!Q1.empty())
    {
        while(!Q1.empty())
        {
            w=Q1.front(); Q1.pop();
            //printf("%d %d %d\n", w.lin,w.col,w.dir);
            if(w.lin==stop.lin && w.col==stop.col)
            {
                ans=min(ans,w.cost);
                continue;
            }
            for(t=-1;t<=1;++t)
            {
                w1.dir=(w.dir+t+8)%8; w1.lin=w.lin+dx[w1.dir]; w1.col=w.col+dy[w1.dir];
                w1.cost=w.cost+(t!=0);
                if(Ok(w1) && dp[w1.lin][w1.col][w1.dir]>w1.cost)
                {
                    dp[w1.lin][w1.col][w1.dir]=w1.cost;
                    if(w1.cost==w.cost) Q1.push(w1);
                    else Q2.push(w1);
                }

                w1.lin=w.lin; w1.col=w.col;
                //printf("%d %d %d\n", w1.lin,w1.col,w1.dir);
                if(dp[w1.lin][w1.col][w1.dir]>w1.cost)
                {
                    dp[w1.lin][w1.col][w1.dir]=w1.cost;
                    if(w1.cost==w.cost) Q1.push(w1);
                    else Q2.push(w1);
                }
            }
        }
        while(!Q2.empty())
        {
            w=Q2.front(); Q2.pop(); Q1.push(w);
        }
    }
}

int main()
{
    int i,j,k;
    freopen ("car.in","r",stdin);
    freopen ("car.out","w",stdout);
    scanf("%d%d%d%d%d%d", &n,&m,&start.lin,&start.col,&stop.lin,&stop.col);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            scanf("%d", &a[i][j]);
            for(k=0;k<=8;++k) dp[i][j][k]=INF;
        }
   Dijkstra();
   if(ans>=INF) printf("-1\n");
   else
   printf("%d\n", ans);
   return 0;
}