Cod sursa(job #2092363)

Utilizator Mihai9Oniga Mihai Mihai9 Data 21 decembrie 2017 16:16:34
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
using namespace std;
int v[507][507],min[8][507][507],car[2056392],sx,sy,sf,fx,fy,q,s,n,m;
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
void add(int sx,int sy,int d,int ct){
 for(int i=sx,j=sy;!v[i][j];i+=dir[d][0],j+=dir[d][1]){
  if(!min[d][i][j]){min[d][i][j]=ct;car[++sf]=(((i<<9)+j)<<3)+d;if((i==fx)&&(j==fy)){s=ct;}}
 }
}
int main (){
 freopen("car.in","r",stdin);
 freopen("car.out","w",stdout);
 scanf("%d%d",&n,&m);
 scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
 for(int i=0;i<=n+1;i++){
  for(int j=0;j<=m+1;j++){v[i][j]=1;}
 }
 for(int i=1;i<=n;i++){
  for(int j=1;j<=m;++j){scanf("%d",&v[i][j]);}
 }
 for(int sf=-1,i=0;i<8;i++){add(sx,sy,i,1);}
 for(int q=0;(q<=sf)&&(!s);++q){
  int i=car[q]>>12,j=(car[q]&4090)>>3,d=car[q]&7;
  add(i,j,(d+1)%8,min[d][i][j]+1);
  add(i,j,(d+8-1)%8,min[d][i][j]+1);
 }printf("%d\n",s-1);
}