Cod sursa(job #797991)

Utilizator JohnPeterJohn Peter JohnPeter Data 15 octombrie 2012 14:37:45
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include<cstdio>
#include<vector>
#include<cassert>
#include<queue>
#include<algorithm>

using namespace std;

int n, m, sx, sy, dsx, dsy, mat[505][505];

struct intz{
  int x, y, z;

  intz(){};

  intz(int xx, int yy, int zz){
    x = xx;
    y = yy;
    z = zz;
  }
};

void read(){
  assert(freopen("car.in", "r", stdin));

  scanf("%d%d", &n, &m);
  scanf("%d%d%d%d\n", &sx, &sy, &dsx, &dsy);

  char s[1010];
  for(int i = 1; i <= n; ++i)
  {
	  gets (s + 1);
	  for(int j = 1; j <= m; ++j)
		  mat[i][j] = s[2 * j - 1] - '0';
  }
}

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dp[8][505][505];

inline int valid(int x, int y, int z){
  if(y <= n && y > 0 && z <= m && z > 0)
    if(mat[y][z] != 1)
        return 1;
  return 0;
}

int ans;

void solve(){
  for(int i = 0; i <= 7; ++i)
    dp[i][sx][sy] = 1;

  queue<intz> q, p;

  for(int i = 0 ; i <= 7; ++i){
    intz t(i,sx,sy);
    p.push(t);
  }

  while(!q.empty() || !p.empty()){
    if(q.empty())
      swap(p, q);

    intz now = q.front();
    q.pop();


    if(valid(now.x, now.y + dx[now.x], now.z + dy[now.x]))
      if(dp[now.x][now.y + dx[now.x]][now.z + dy[now.x]] == 0 || dp[now.x][now.y + dx[now.x]][now.z + dy[now.x]] > dp[now.x][now.y][now.z]){
        dp[now.x][now.y + dx[now.x]][now.z + dy[now.x]] = dp[now.x][now.y][now.z];
        intz ns(now.x, now.y + dx[now.x], now.z + dy[now.x]);
        q.push(ns);
      }

    int np = (now. x + 1) & 7;

    if(valid(np, now.y, now.z))
     if(dp[np][now.y][now.z] == 0 || dp[now.x][now.y][now.z] + 1 < dp[np][now.y][now.x]){
       dp[np][now.y][now.z] = dp[now.x][now.y][now.z] + 1;
       intz ns(np, now.y, now.z);
       p.push(ns);
     }

    np = (now.x - 1 + 8) & 7;

    if(valid(np, now.y, now.z))
     if(dp[np][now.y][now.z] == 0 || dp[now.x][now.y][now.z] + 1 < dp[np][now.y][now.x]){
       dp[np][now.y][now.z] = dp[now.x][now.y][now.z] + 1;
       intz ns(np, now.y, now.z);
       p.push(ns);
     }

  }

  for(int i = 0; i < 8; ++i)
    if(dp[i][dsx][dsy] != 0)
      ans = dp[i][dsx][dsy];

  for(int i = 0; i < 8; ++i)
    if(dp[i][dsx][dsy] != 0)
      ans = min(ans, dp[i][dsx][dsy]);
}

void write(){
  assert(freopen("car.out", "w", stdout));

  printf("%d", ans - 1);
}

int main(){
  read();
  solve();
  write();

  return 0;
}