Cod sursa(job #396901)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 16 februarie 2010 04:11:37
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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];
int dir[N][N];
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)
{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,n,m;
 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;
   cost[i][j]=INF;
  }
 }

 cost[sx][sy]=0;
 for (i=0;i<8;i++)
 {tx=dx[i]+sx;
  ty=dy[i]+sy;
  if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&!a[tx][ty])
  {dir[tx][ty]=i;
   cost[tx][ty]=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])
   {if(cost[p.x][p.y]+f(dir[p.x][p.y],i)<cost[tx][ty])
    {cost[tx][ty]=cost[p.x][p.y]+f(dir[p.x][p.y],i);
     dir[tx][ty]=i;
     q.push_back(nod(tx,ty));
    }
   }
  }
 }

 printf("%d",cost[fx][fy]);

 return 0;
}