Cod sursa(job #28764)

Utilizator lucibitLucian Onea lucibit Data 8 martie 2007 11:29:24
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<stdio.h>
#define maxN 500
#define inf 10000
int a[maxN][maxN],d[maxN][maxN],viz[maxN][maxN],si,sj,fi,fj,n,m;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};


long int c[maxN][maxN];
void citeste()
{freopen("car.in","r",stdin);
 scanf("%d %d\n",&n,&m);
 scanf("%d %d %d %d\n",&si,&sj,&fi,&fj);
 int i,j;
 for(i=1;i<=n;i++)
 { for(j=1;j<=m;j++) {scanf("%d ",&a[i][j]); c[i][j]=inf; }
 scanf("\n");
 }
 }
void lee()
{int rot,ii,jj,t,Q[250000][2];
 long int cap,coada;

 cap=coada=1;
 Q[cap][0]=si;
 Q[cap][1]=sj;
 c[si][sj]=d[si][sj]=0;
 for(t=0;t<=7;t++)
 {ii=si+dir[t][0];
  jj=si+dir[t][1];
  if(!a[ii][jj] && ii<n+1 && ii>0 && jj<m+1&& jj>0)
		{if(t<4) d[ii][jj]=t+4;
						else  d[ii][jj]=t-4;

						Q[++coada][0]=ii;
						Q[coada][1]=jj;
					  c[ii][jj]=0;
					  viz[ii][jj]=1;
					  }
  }
 viz[si][sj]=1;
 cap++;
 while (cap<=coada)
 {for(t=0;t<=7;t++)
  {rot=(d[ Q[cap][0] ][ Q[cap][1] ]+t)%8;
	ii=Q[cap][0]+dir[ rot ][0];
	jj=Q[cap][1]+dir[ rot ][1];
	if(!a[ii][jj] && ii<n+1 && ii>0 && jj<m+1&& jj>0)
						{if(!viz[ii][jj]){Q[++coada][0]=ii; Q[coada][1]=jj; viz[ii][jj]=1;}
						 if(t==0 && c[Q[cap][0]][Q[cap][1]]+4<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+4;
																							if(rot<4) d[ii][jj]=rot+4;
																							else  d[ii][jj]=rot-4;
																							}
						 if((t==1 ||t==7) && c[Q[cap][0]][Q[cap][1]]+3<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+3;
																							if(rot<4) d[ii][jj]=rot+4;
																							else  d[ii][jj]=rot-4;
																							}
						 if((t==2 ||t==6) && c[Q[cap][0]][Q[cap][1]]+2<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+2;
																							if(rot<4) d[ii][jj]=rot+4;
																							else  d[ii][jj]=rot-4;
																							}
						 if((t==3 ||t==5) && c[Q[cap][0]][Q[cap][1]]+1<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+1;
																							if(rot<4) d[ii][jj]=rot+4;
																							else  d[ii][jj]=rot-4;
																							}
						 if(t==4 && c[Q[cap][0]][Q[cap][1]]<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]];
																							if(rot<4) d[ii][jj]=rot+4;
																							else  d[ii][jj]=rot-4;
																							}



						  }

	 }
  cap++;
  }

 }
int main ()
{int i;
 citeste();
 for(i=0;i<=n;i++) {a[i][0]=1; a[i][m+1]=1;}
 for(i=0;i<=m;i++) {a[0][i]=1; a[n+1][i]=1;}
 lee();
 freopen("car.out","w",stdout);
 printf("%ld\n",c[fi][fj]);
 return 0;
 }