Cod sursa(job #338963)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 august 2009 16:53:35
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <stdio.h>
#include <queue>
using namespace std;
#define Nmax 505
#define INF 2000000000
#define x first 
#define y second 

int A[Nmax][Nmax];
int v[Nmax][Nmax],d[Nmax][Nmax][8];
queue< pair<int,int> > Q;
int n,m,xi,yi,xf,yf;
const int dx[8]={-1,-1,0,1,1,1,0,-1};
const int dy[8]={0,1,1,1,0,-1,-1,-1};
const int cst[8]={0,1,2,3,4,3,2,1};

void read(){
     int i,j;
     freopen("car.in","r",stdin);
     freopen("car.out","w",stdout);
     scanf("%d%d\n",&n,&m);
     scanf("%d%d%d%d",&xi,&yi,&xf,&yf);
     for(i=1;i<=n;++i)
       for(j=1;j<=m;++j)
                         scanf("%d",&A[i][j]);
}

int cost(pair <int,int> p,int kk){
    int k,x,y,min=INF;
    x=p.x; y=p.y;
    for(k=1;k<=d[x][y][0];k++)
      if(cst[abs(kk-d[x][y][k])] < min)
        min=cst[abs(kk-d[x][y][k])];
    return min;
}

int in_oras(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m) return 0;
    return 1;
}

void work(){
     int k,xx,yy;
     pair<int,int> p;
     v[xi][yi]=1;
     p=make_pair(xi,yi);
     for(k=0;k<8;k++){
                      xx=p.x+dx[k];
                      yy=p.y+dy[k];
                      if(in_oras(xx,yy) && !A[xx][yy]){
                        d[xx][yy][0]=1,d[xx][yy][1]=k,v[xx][yy]=1;
                        Q.push(make_pair(xx,yy));
                        }
                        }

     while(!Q.empty()){
                       p=Q.front();
                      for(k=0;k<8;k++){
                                        xx=p.x+dx[k];
                                        yy=p.y+dy[k];
                                        if(in_oras(xx,yy) && !A[xx][yy] ){
                                                      if(!v[xx][yy]){    
                                                         v[xx][yy]=v[p.x][p.y]+cost(p,k);
                                                        d[xx][yy][0]=1;
                                                        d[xx][yy][1]=k;
                                                       Q.push(make_pair(xx,yy));
                                                        }
                                                      else
                                                      if(v[xx][yy]>v[p.x][p.y]+cost(p,k)){
                                                        v[xx][yy]=v[p.x][p.y]+cost(p,k);
                                                        d[xx][yy][0]=1;
                                                        d[xx][yy][1]=k;
                                                       Q.push(make_pair(xx,yy));
                                                        }
                                                       else
                                                      if(v[xx][yy]==v[p.x][p.y]+cost(p,k)){
                                                        d[xx][yy][0]++;
                                                        d[xx][yy][d[xx][yy][0]]=k;
                                                     //  Q.push(make_pair(xx,yy));
                                                        }
                                                       
                                               //       printf("in %d %d este v %d si d %d\n",xx,yy,
                                              //               v[xx][yy],d[xx][yy]);
                                                       }
                                        }
                       Q.pop();
                       }
}

void write(){
     printf("%d\n",v[xf][yf]-1);
     fclose(stdin); fclose(stdout);
}

int main(){
    read();          
    work();
    write();
    return 0;
}