Cod sursa(job #648957)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 14 decembrie 2011 21:07:28
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 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};

bool a[N][N], f[N][N][D][2];

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[2];

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[0].push(node(sx, sy, d));
    dist[sx][sy][d] = 0;
  }

  bool p = 1;

  while (Q[0].size() + Q[1].size() > 0) {  
    p = 1 - p;

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

      if (nc.x == fx && nc.y == fy) {
        printf("%d\n", dist[nc.x][nc.y][nc.d]);
        return;
      }

      //next
      nn.x = nc.x;
      nn.y = nc.y;
      nn.d = (nc.d + 1) % 8;
      if (dist[nn.x][nn.y][nn.d] > dist[nc.x][nc.y][nc.d] + 1) {
        dist[nn.x][nn.y][nn.d] = dist[nc.x][nc.y][nc.d] + 1;
        if (!f[nn.x][nn.y][nn.d][1 - p]) {
          Q[1 - p].push(nn);
          f[nn.x][nn.y][nn.d][1 - p] = 1;
        }
      }

      //previous
      nn.x = nc.x;
      nn.y = nc.y;
      nn.d = (nc.d - 1 + 8) % 8;
      if (dist[nn.x][nn.y][nn.d] > dist[nc.x][nc.y][nc.d] + 1) {
        dist[nn.x][nn.y][nn.d] = dist[nc.x][nc.y][nc.d] + 1;
        if (!f[nn.x][nn.y][nn.d][1 - p]) {
          Q[1 - p].push(nn);
          f[nn.x][nn.y][nn.d][1 - p] = 1;
        }
      }

      //miscare
      nn.x = nc.x + dx[nc.d];
      nn.y = nc.y + dy[nc.d];
      nn.d = nc.d;
      if (!a[nn.x][nn.y] && dist[nn.x][nn.y][nn.d] > dist[nc.x][nc.y][nc.d]) {
        dist[nn.x][nn.y][nn.d] = dist[nc.x][nc.y][nc.d]; 
        if (!f[nn.x][nn.y][nn.d][p]) {
          Q[p].push(nn);
          f[nn.x][nn.y][nn.d][p] = 1;
        }
      }
    }
  }

  printf("-1\n");
}

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

  read();

  bordeaza();

  solve();

  return 0;
}