Cod sursa(job #1328104)

Utilizator MKLOLDragos Ristache MKLOL Data 28 ianuarie 2015 00:41:08
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

struct cel{
  int x,y,z;
};
int N,M,x1,x2,y1,y2;
queue<cel> qu;
int v[505][505];
int best[505][505][8];

int move(int x,int y,int z){
  
  int xa=x,ya=y;
  while(v[xa][ya] == 1){
    
    if(best[xa+dx[z]][ya+dy[z]][z]==0 && v[xa+dx[z]][ya+dy[z]] == 1){
      cel ax;
      ax.x=xa+dx[z];
      ax.y=ya+dy[z];
      ax.z=z;
      qu.push(ax);
      best[xa+dx[z]][ya+dy[z]][z] = best[xa][ya][z];
      xa=xa+dx[z];
      ya=ya+dy[z];
    } else break;
  }
  int z1 = (z+1)%8;
  int z2 = ((z-1)+8)%8;
  if(best[x][y][z1]==0){
    cel ax;
    ax.x=x;
    ax.y=y;
    ax.z=z1;
    qu.push(ax);
    best[x][y][z1] = 1 + best[x][y][z];
  }
  if(best[x][y][z2]==0){
    cel ax;
    ax.x=x;
    ax.y=y;
    ax.z=z2;
    qu.push(ax);
    best[x][y][z2] = 1 + best[x][y][z];
  }
}

int main(){
  freopen("car.in","r",stdin);
  freopen("car.out","w",stdout);
  scanf("%d%d",&N,&M);
  scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  for(int i=1;i<=N;++i){
    for(int j=1;j<=M;++j)
      {
        scanf("%d",&v[i][j]);
        v[i][j]^=1;
      }
  }
  for(int i=0;i<8;++i){
    cel ax;
    ax.x=x1;
    ax.y=y1;
    ax.z=i;
    qu.push(ax);
    best[x1][y1][i]=1;
  }
  while(!qu.empty()){
    cel a = qu.front();
    qu.pop();
    //printf("%d %d %d %d\n",a.x,a.y,a.z, best[a.x][a.y][a.z]);
    move(a.x,a.y,a.z);
  }
  int ret = N*M*8+1;
  for(int i=0;i<8;++i){
    ret=min(ret,best[x2][y2][i]);
  }
  printf("%d",ret);
}