Cod sursa(job #1423530)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 21 aprilie 2015 22:27:24
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include <fstream>
#include <cstring>
#define DIM 520
using namespace std;

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

int N, M, i, j, K, ok, minim, p, u;
int A[DIM][DIM], D[DIM][DIM][9];
int F[DIM][DIM], ist, jst, ifi, jfi;
int C[3][DIM*DIM], d, iv, jv, jc, ic;

int diri[] = {-1,-1,-1, 0, 1, 1, 1, 0};
int dirj[] = {-1, 0, 1, 1, 1, 0,-1,-1};

void SetUp(){
     fin >> N >> M;
     fin >> ist >> jst;
     fin >> ifi >> jfi;
     for(i = 1; i <= N; i ++)
          for(j = 1; j <= M; j ++)
               fin >> A[i][j];
     memset(D, -1, sizeof(D));
     p = 2; u = 1;
     C[1][u] = ist;
     C[2][u] = jst;
     F[ist][jst] = 2;
     memset(D[ist][jst], 0, sizeof(D[ist][jst]));
     for(d = 0; d <= 7; d ++){
          iv = ist + diri[d];
          jv = jst + dirj[d];
          if(iv >= 1 && iv <= N)
               if(jv >= 1 && jv <= M)
                    if(A[iv][jv] == 0){
                         u ++;
                         C[1][u] = iv;
                         C[2][u] = jv;
                         F[iv][jv] = 2;
                         D[iv][jv][d] = 0;
                    }
     }
     return;
}

void BFS(){
     while(p <= u){
          ic = C[1][p];
          jc = C[2][p];
          F[ic][jc] = 2;
          for(d = 0; d <= 7; d ++){
               iv = ic + diri[d];
               jv = jc + dirj[d];
               if(iv >= 1 && iv <= N)
                    if(F[iv][jv] != 2)
                         if(jv >= 1 && jv <= M)
                              if(A[iv][jv] == 0){
                                   if(F[iv][jv] == 0){
                                        u ++;
                                        C[1][u] = iv;
                                        C[2][u] = jv;
                                        F[iv][jv] = 1;
                                   }
                                   if(D[iv][jv][d] == -1)
                                        D[iv][jv][d] = DIM*DIM;
                                   if(D[iv][jv][d] > D[ic][jc][(d+8)%8] + 0 && D[ic][jc][(d+8)%8] != -1)
                                        D[iv][jv][d] = D[ic][jc][(d+8)%8] + 0;
                                   if(D[iv][jv][d] > D[ic][jc][(d+9)%8] + 1 && D[ic][jc][(d+9)%8] != -1)
                                        D[iv][jv][d] = D[ic][jc][(d+9)%8] + 1;
                                   if(D[iv][jv][d] > D[ic][jc][(d+7)%8] + 1 && D[ic][jc][(d+7)%8] != -1)
                                        D[iv][jv][d] = D[ic][jc][(d+7)%8] + 1;
                                   if(D[iv][jv][d] > D[ic][jc][(d+10)%8] + 2 && D[ic][jc][(d+10)%8] != -1)
                                        D[iv][jv][d] = D[ic][jc][(d+10)%8] + 2;
                                   if(D[iv][jv][d] > D[ic][jc][(d+6)%8] + 2 && D[ic][jc][(d+6)%8] != -1)
                                        D[iv][jv][d] = D[ic][jc][(d+6)%8] + 2;
                              }
          }
          p ++;
     }
     return;
}

void Finish(){
     minim = DIM * DIM;
     for(d = 0; d <= 7; d ++)
          if(D[ifi][jfi][d] < minim && D[ifi][jfi][d] != -1)
               minim = D[ifi][jfi][d];
     minim = DIM * DIM;
     if(minim == DIM * DIM)
          fout << -1;
     else
          fout << minim;
     return;
}

int main(){
     SetUp();
     BFS();
     Finish();
     return 0;
}