Cod sursa(job #1068212)

Utilizator vlad_DVlad Dumitriu vlad_D Data 28 decembrie 2013 00:57:06
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
int N, M;
int v[512][512];
int dp[512][512][8];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int sx, sy, ex, ey;
int qx[1000000];
int qy[1000000];
int coada[512][512];
int main() {
  freopen("car.in", "r", stdin);
  freopen("car.out", "w", stdout);
  scanf("%d %d", &N, &M);
  scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= M; ++j) scanf("%d", &v[i][j]);
  for (int i = 0; i <= N + 1; ++i) v[i][0] = v[i][M+1] = 1;
  for (int i = 0; i <= M + 1; ++i) v[0][i] = v[N+1][i] = 1;
  memset(dp, 333, sizeof(dp));
  int INF = dp[0][0][0];
  for (int i = 0; i < 8; ++i) dp[sx][sy][i] = 0;
  qx[++qx[0]] = sx; qy[++qy[0]] = sy;
  coada[sx][sy] = 1;
  int best = INF;
  for (int i = 1; i <= qx[0]; ++i) {
    int nx = qx[i], ny = qy[i];
    coada[nx][ny] = 0;
    if (nx == ex && ny == ey)
      for (int d = 0; d < 8; ++d) best = min(best, dp[nx][ny][d]);
    for (int d = 0; d < 16; ++d) dp[nx][ny][d%8] = min(dp[nx][ny][d%8],1+min(dp[nx][ny][(d+7)%8], dp[nx][ny][(d+1)%8]));
    for (int d = 0; d < 8; ++d) if (dp[nx][ny][d] < best) {
      if (v[nx+dx[d]][ny+dy[d]] == 0 && dp[nx+dx[d]][ny+dy[d]][d] > dp[nx][ny][d]) {
        dp[nx+dx[d]][ny+dy[d]][d] = dp[nx][ny][d];
        if (!coada[nx + dx[d]][ny + dy[d]]) qx[++qx[0]] = nx + dx[d], qy[++qy[0]] = ny + dy[d], coada[nx+dx[d]][ny+dy[d]]=1;
      }
    }
  }
  printf("%d\n", best >= INF ? -1 : best);
  return 0;
}