Cod sursa(job #2724075)

Utilizator PetyAlexandru Peticaru Pety Data 16 martie 2021 13:16:54
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O1")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
 
 
using namespace std;
 
ifstream fin ("car.in");
ofstream fout ("car.out");

const int ct = 100000;
const int inf = 1e9;

int dist[502][502][8], n, m, v[502][502];
int dl[] = {0, 0, -1, -1, -1, 1, 1, 1};
int dc[] = {-1, 1, 0, -1, 1, 0, -1, 1};

struct lol {
  int dist, x, y, dir;
};

struct cmp {
  bool operator () (const lol &a, const lol &b) {
    return a.dist > b.dist;
  }
};

bool lol1 (int x, int y) {
  return (x >= 1 && x <= n && y >= 1 && y <= m && !v[x][y]);
}

int main () 
{
  fin >> n >> m;
  int x1, y1, x2, y2;
  fin >> x1 >> y1 >> x2 >> y2;
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++)
      fin >> v[i][j];
  priority_queue<lol, vector<lol>, cmp>pq;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      for (int k = 0; k < 8; k++)
        dist[i][j][k] = inf;
  for (int i = 0; i < 8; i++) {
    dist[x1][y1][i] = 0;
    pq.push({0, x1, y1, i});
  }
  while (pq.size()) {
    auto p = pq.top();
    pq.pop();
    if (p.dist != dist[p.x][p.y][p.dir])
      continue;
    for (int i = 0; i < 8; i++) {
      int i1 = p.x + dl[i];
      int j1 = p.y + dc[i];
      if (lol1(i1, j1) && dist[i1][j1][i] > p.dist + abs(dl[p.dir] - dl[i]) + abs(dc[p.dir] - dc[i])) {
        dist[i1][j1][i] = p.dist + abs(dl[p.dir] - dl[i]) + abs(dc[p.dir] - dc[i]);
        pq.push({dist[i1][j1][i], i1, j1, i});
      }
    }
  }
  int ans = inf;
  for (int i = 0; i < 8; i++)
    ans = min(ans, dist[x2][y2][i]);
  if (ans == inf)
    fout << -1;
  else
    fout << ans;
  return 0;
}