Cod sursa(job #217986)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 31 octombrie 2008 12:36:44
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include  <fstream>
#include <math.h>
#include <queue>
#define MAX 503
#define inf 0x3f3f3f

using namespace std;

ifstream fin ("car.in");
ofstream fout ("car.out");

struct str
{
     int l,c;
};

queue <str> Q;

const int val[9][9]={{0,0,0,0,0,0,0,0,0},{0,0,1,2,3,4,3,2,1},{0,1,0,1,2,3,4,3,2},{0,2,1,0,1,2,3,4,3},{0,3,2,1,0,1,2,3,4},{0,4,3,2,1,0,1,2,3},{0,3,4,3,2,1,0,1,2},{0,2,3,4,3,2,1,0,1},{0,1,2,3,4,3,2,1,0}};
const int x[11]={0,-1,-1,-1,0,1,1,1,0};
const int y[11]={0,-1,0,1,1,1,0,-1,-1};

int cost[MAX][MAX];
int m[MAX][MAX];
int dir[MAX][MAX];
int n,M;
int ix,iy,fx,fy;

void citire()
{
     fin>>n>>M;
     fin>>ix>>iy>>fx>>fy;
     for (int i=1;i<=n;i++)
          for (int j=1;j<=M;j++)
          {
               fin>>m[i][j];
               m[i][j]=1-m[i][j];
          }
}

inline int va(int a,int b)
{
     return val[a][b];
}

void rezultat()
{
     memset(cost,inf, sizeof cost);
     str val,aux;
     val.c=iy;
     val.l=ix;
     cost[val.l][val.c]=0;
     Q.push(val);
     while (!Q.empty())
     {
          val=Q.front();
          Q.pop();
          for (int i=1;i<=8;i++)
          {
               if (m[val.l+x[i]][val.c+y[i]]==1)
               {
                    if (cost[val.l+x[i]][val.c+y[i]] >cost[val.l][val.c] + va(dir[val.l][val.c],i))
                    {
                         cost[val.l+x[i]][val.c+y[i]]=cost[val.l][val.c] + va(dir[val.l][val.c],i);
                         aux.l=val.l+x[i];
                         aux.c=val.c+y[i];
                         dir[val.l+x[i]][val.c+y[i]]=i;
                         Q.push(aux);
                    }
               }
          }
     }
}

int main ()
{
     citire();
     rezultat();
     if (cost[fx][fy])
     fout<<cost[fx][fy]<<"\n";
     else
          fout<<-1;
     return 0;
}