Cod sursa(job #396902)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 16 februarie 2010 04:54:48
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdlib.h>
#include <stdio.h>
#include <deque>
#define INF 0x7f7f7f7f
#define N 501

using namespace std;
bool a[N][N];
int cost[N][N][8];
int dx[8]={0,1,1, 1, 0,-1,-1,-1};
int dy[8]={1,1,0,-1,-1,-1, 0, 1};

struct nod
{int x,y;
 nod(int a,int b)
 {x=a;y=b;
 }
 nod()
 {}
};

int f(int x,int y)//costul dintre doua directii
                  //f(delta)=0 1 2 3 4 3 2 1
{return abs(4-abs(4-abs(x-y)));
}

int main ()
{freopen("car.in","r",stdin);
 freopen("car.out","w",stdout);
 int sx,sy,fx,fy,x,tx,ty;
 int i,j,k,n,m,min,imin,flag;
 deque<nod> q;
 nod p;
 scanf("%d %d",&n,&m);
 scanf("%d %d %d %d",&sx,&sy,&fx,&fy);
 
 for (i=1;i<=n;i++)
 {for (j=1;j<=m;j++)
  {scanf("%d",&x);
   a[i][j]=x;
   for (k=0;k<8;k++)
   {cost[i][j][k]=INF;
   }
  }
 }

 


 for (i=0;i<8;i++)
 {cost[sx][sy][i]=0;
  tx=dx[i]+sx;
  ty=dy[i]+sy;
  if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&!a[tx][ty])
  {cost[tx][ty][i]=0;
   q.push_back(nod(tx,ty));
  }
 }

 while(!q.empty())
 {p=q.front();q.pop_front();
  for (i=0;i<8;i++)
  {tx=p.x+dx[i];
   ty=p.y+dy[i];

   if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&!a[tx][ty])
   {flag=0;
    for (j=0;j<8;j++)
    {if(cost[tx][ty][i]>cost[p.x][p.y][j]+f(j,i))
     {cost[tx][ty][i]=cost[p.x][p.y][j]+f(j,i);
      flag=1;
     }
    }
    if(flag)
    {q.push_back(nod(tx,ty));
    }
   }
  }
 }
 /*
 for (i=1;i<=4;i++)
 {for (j=1;j<=4;j++)
  {/*if(cost[i][j]==INF)
   {printf("X ");
   }
   else
   {printf("%d ",cost[i][j]);
   }
   printf("%d ",a[i][j]);
  }
  printf("\n");
 }
 */
 min=INF;
 for (i=0;i<8;i++)
 {if(cost[fx][fy][i]<min)
  {min=cost[fx][fy][i];
  }
 }
 
 printf("%d",min);

 return 0;
}