Cod sursa(job #648938)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 decembrie 2011 20:34:07
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 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 dx[D] = {-1,-1, 0, 1, 1, 1, 0,-1};
int dy[D] = { 0, 1, 1, 1, 0,-1,-1,-1};
int c[D][D] = {{ 0, 1, 2, 3, 4, 3, 2, 1},
               { 1, 0, 1, 2, 3, 4, 3, 2},
               { 2, 1, 0, 1, 2, 3, 4, 3},
               { 3, 2, 1, 0, 1, 2, 3, 4},
               { 4, 3, 2, 1, 0, 1, 2, 3},
               { 3, 4, 3, 2, 1, 0, 1, 2},
               { 2, 3, 4, 3, 2, 1, 0, 1},
               { 1, 2, 3, 4, 3, 2, 1, 0}};

bool a[N][N], f[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;
}

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;
    f[sx][sy][d] = 1;
  }

  int rez = INF;
  
  while (!Q.empty()) {
    nc = Q.front();
    Q.pop();
    f[nc.x][nc.y][nc.d] = 0;

    for (int i = 0; i <= 7; ++i) 
      if (c[nc.d][i] < 3)
      {
        nn.x = nc.x + dx[i];
        nn.y = nc.y + dy[i];
        nn.d = i;

        if (!a[nn.x][nn.y] && dist[nn.x][nn.y][nn.d] > dist[nc.x][nc.y][nc.d] + c[nc.d][i]) {
          dist[nn.x][nn.y][nn.d] = dist[nc.x][nc.y][nc.d] + c[nc.d][i];
          
          if (nn.x == fx && nn.y == fy) 
            rez = dist[nn.x][nn.y][nn.d];
          
          if (!f[nn.x][nn.y][nn.d] && dist[nn.x][nn.y][nn.d] < rez) {
            Q.push(nn);
            f[nn.x][nn.y][nn.d] = 1;
          }
        }
      }
  }

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

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

  read();

  bordeaza();

  solve();

  return 0;
}