Cod sursa(job #338930)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 7 august 2009 15:33:48
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <stdio.h>
#include <queue>
using namespace std;
#define Nmax 505
#define x first 
#define y second 

int A[Nmax][Nmax];
int v[Nmax][Nmax],d[Nmax][Nmax];
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 cost[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 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]=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[abs(d[p.x][p.y]-k)];
                                                        d[xx][yy]=k;
                                                       Q.push(make_pair(xx,yy));
                                                        }
                                                      else
                                                      if(v[xx][yy]>v[p.x][p.y]+cost[abs(d[p.x][p.y]-k)]){
                                                        v[xx][yy]=v[p.x][p.y]+cost[abs(d[p.x][p.y]-k)];
                                                        d[xx][yy]=k;
                                                        }
                                               //       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;
}