Cod sursa(job #2922636)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 9 septembrie 2022 12:09:18
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>

#define NMAX 500
#define INFINIT 2000000 //doua milioane = 500 * 500 * 8

/*
   0 1 2
   7   3
   6 5 4
*/

using namespace std;

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

struct elem{
   int x, y, dir;
};

int N, M;
int Si, Sj, Fi, Fj;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int v[NMAX + 1][NMAX + 1];
int dp[NMAX + 2][NMAX + 2][8];
deque <elem> Q;

inline int inside(int x, int y){
   return x >= 1 && x <= N && y >= 1 && y <= M;
}

void Solve(){
   for(int i = 0; i <= 7; i++){
      Q.push_back(elem{Si, Sj, i});
      dp[Si][Sj][i] = 0;
   }

   while(!Q.empty()){
      int x = Q.front().x;
      int y = Q.front().y;
      int dir = Q.front().dir;
      Q.pop_front();

      int xn = x + dx[dir];
      int yn = y + dy[dir];
      if(inside(xn, yn) && v[xn][yn] == 0 && dp[x][y][dir] < dp[xn][yn][dir]){
         dp[xn][yn][dir] = dp[x][y][dir];
         Q.push_front(elem{xn, yn, dir});
      }

      int dir1 = (dir - 1 + 8) % 8;
      int dir2 = (dir + 1) % 8;
      if(dp[x][y][dir] + 1 < dp[x][y][dir1]){
         dp[x][y][dir1] = dp[x][y][dir] + 1;

         Q.push_back(elem{x, y, dir1});
      }
      if(dp[x][y][dir] + 1 < dp[x][y][dir2]){
         dp[x][y][dir2] = dp[x][y][dir] + 1;

         Q.push_back(elem{x, y, dir2});
      }
   }
}

int main()
{
   fin >> N >> M;

   fin >> Si >> Sj >> Fi >> Fj;

   for(int i = 1; i <= N; i++){
      for(int j = 1; j <= M; j++){
         fin >> v[i][j];
      }
   }

   for(int i = 1; i <= N; i++){
      for(int j = 1; j <= M; j++){
         for(int k = 0; k <= 7; k++){
            dp[i][j][k] = INFINIT;
         }
      }
   }

   Solve();

   int rez = INFINIT;
   for(int k = 0; k <= 7; k++){
      rez = min(rez, dp[Fi][Fj][k]);
   }

   if(rez == INFINIT){
      fout << -1 << "\n";
   }
   else {
      fout << rez << "\n";
   }
   return 0;
}