Cod sursa(job #648922)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 decembrie 2011 20:12:26
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
//Test graf
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct pct {
  int x, y, d;
};

const int N = 505, D = 8, INF = 0x3f3f3f3f;

int n, m, sx, sy, fx, fy, dist[N][N][D];

int dl[D] = { 1, 1, 0,-1,-1,-1, 0, 1};
int dc[D] = { 0,-1,-1,-1, 0, 1, 1, 1};

bool a[N][N];

vector <pair <pct, int> > L[N][N][D]; 

void read() {
  char s[2 * N];

  scanf("%d%d\n", &n, &m);
  scanf("%d%d%d%d\n", &sx, &sy, &fx, &fy);

  for (int i = 1; i <= n; ++i) {
    fgets(s, 2 * N, stdin);
    for (int j = 1; j <= m; ++j)
      a[i][j] = s[2 * (j - 1)] - '0';
  }
}

pct node(int x, int y, int d) {
  pct r;
  
  r.x = x;
  r.y = y;
  r.d = d;

  return r;
}

void bordeaza() {
  for (int i = 0; i <= n + 1; ++i)
    a[i][0] = a[i][m + 1] = 1;
  
  for (int j = 0; j <= m + 1; ++j)
    a[0][j] = a[n + 1][j] = 1;
}

void init() {
  bordeaza();

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      L[i][j][0].push_back(make_pair(node(i, j, 7), 1));
      L[i][j][0].push_back(make_pair(node(i, j, 1), 1));

      for (int d = 1; d <= 6; ++d) {
        L[i][j][d].push_back(make_pair(node(i, j, d - 1), 1));
        L[i][j][d].push_back(make_pair(node(i, j, d + 1), 1));
      }

      L[i][j][7].push_back(make_pair(node(i, j, 6), 1));
      L[i][j][7].push_back(make_pair(node(i, j, 0), 1));

      for (int d = 0; d <= 7; ++d)
        if (!a[i + dl[d]][j + dc[d]])
          L[i][j][d].push_back(make_pair(node(i + dl[d], j + dc[d], d), 0));
    }
}

queue <pct> Q;

void solve() {
  pct nc, nn;

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      for (int d = 0; d <= 7; ++d)
        dist[i][j][d] = INF;

  for (int d = 0; d <= 7; ++d) {
    Q.push(node(sx, sy, d));
    dist[sx][sy][d] = 0;
  }
  
  while (!Q.empty()) {
    nc = Q.front();
    Q.pop();
    
    for (int i = 0; i < (int)L[nc.x][nc.y][nc.d].size(); ++i) {
      nn = L[nc.x][nc.y][nc.d][i].first;
      if (dist[nn.x][nn.y][nn.d] > dist[nc.x][nc.y][nc.d] + L[nc.x][nc.y][nc.d][i].second) {
        dist[nn.x][nn.y][nn.d] = dist[nc.x][nc.y][nc.d] + L[nc.x][nc.y][nc.d][i].second;
        Q.push(nn);
      }
    }
  }

  int rez = INF;
  
  for (int d = 0; d <= 7; ++d)
    if (rez > dist[fx][fy][d])
      rez = dist[fx][fy][d];

  if (rez != INF)
    printf("%d\n", rez);
  else
    printf("-1\n");
}

int main() {
  freopen("car.in", "r", stdin);
  freopen("car.out", "w", stdout);

  read();

  init();

  solve();

  return 0;
}