Cod sursa(job #600952)

Utilizator cosmyoPaunel Cosmin cosmyo Data 4 iulie 2011 14:17:56
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <queue>
#include <cstring>
#define mp make_pair
#define f first
#define s second

using namespace std;

const int inf=10000000;
int n,m,si,sj,fi,fj,a[505][505],mn[505][505],v[505][505];
int dl[8]={-1,-1,0,1,1,1,0,-1};
int dc[8]={0,1,1,1,0,-1,-1,-1};
int st[8]={0,1,2,3,4,3,2,1};
int unit[10][10];
queue<int> dir;
queue< pair<int,int> > q;

void init()
{int i,j,k;
  for(i=0;i<8;++i)
    unit[0][i]=st[i];
   for(i=1;i<8;++i)
        {
            for(j=i-1,k=7;j>=0;--j,--k)
                unit[i][j]=st[k];
            for(j=i,k=0;j<8;++j,++k)
                unit[i][j]=st[k];
        }
    /*for(i = 0; i < 8; ++i){
        for(j = 0; j < 8; ++j)
            printf("%d ", unit[i][j]);
            printf("\n");
    }*/
}
int cond(int i,int j)
{ if(i<=n&&i>=1&&j<=m&&j>=1&&a[i][j]==0)
    return 1;
 return 0;
}
void solve()
{int i,j,k,l,c,d;
  for(i=0;i<=n+1;++i)
    for(j=0;j<=m+1;++j)
        mn[i][j]=inf;
        mn[si][sj]=0;
    for(k=0;k<8;++k)
        {i=si+dl[k];
         j=sj+dc[k];

                if(cond(i,j))
                    mn[i][j]=unit[k][k],q.push(mp(i,j)),dir.push(k);
        }

    while(!q.empty())
    {l=(q.front()).f;
     c=(q.front()).s;
     d=dir.front();
        for(k=0;k<8;++k)
            {i=l+dl[k];
             j=c+dc[k];

                if(cond(i,j)&&mn[l][c]+unit[d][k]<mn[i][j])
                    {mn[i][j]=mn[l][c]+unit[d][k];
                     q.push(mp(i,j));dir.push(k);
                    }
            }
        v[l][c]=0;
        q.pop();dir.pop();
    }
}


int main()
{freopen("car.in","r",stdin);
 freopen("car.out","w",stdout);
  int i,j;
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&si,&sj,&fi,&fj);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                scanf("%d",&a[i][j]);
     init();
     if(a[si][sj]==0&&a[fi][fj]==0)
      {  solve();
          if(mn[fi][fj]==inf)
            mn[fi][fj]=-1;
      }
      else
        mn[fi][fj]=-1;

     printf("%d\n",mn[fi][fj]);
    return 0;
}