Cod sursa(job #5974)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 16 ianuarie 2007 15:52:33
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
# include <stdio.h>

const int MAXN=500; //AICI!!!! 500
const int MAXDIR=8;
const int vx[9]={0,-1,-1,0,1,1,1,0,-1};
const int vy[9]={0,0,1,1,1,0,-1,-1,-1};
typedef struct NOD{int x, y, dir,cost;};
char a[MAXN+1][MAXN+1][MAXDIR+1];
const long int MAXH=500000; //AICI!!!! 500000
typedef NOD HEAP[MAXH+1];
HEAP heap;
int n,m,xi,yi,xf,yf;

void citire()
{
int i,j,w;
FILE *f=fopen("car.in","r");
fscanf(f,"%d%d",&n,&m);
fscanf(f,"%d%d%d%d",&xi,&yi,&xf,&yf);
for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		{
		fscanf(f,"%d",&w);
		a[i][j][0]=(char)w;
		a[i][j][1]=a[i][j][2]=a[i][j][3]=a[i][j][4]=a[i][j][5]=a[i][j][6]=a[i][j][7]=a[i][j][8]=a[i][j][0];
		}
fclose(f);
}

void scrie(int sol) {FILE *g=fopen("car.out","w");fprintf(g,"%d\n",sol);fclose(g);}

int new_dir(int dir, int dev)
{
int sol=dir+dev;
if (sol<=0) sol+=8; else if (sol>8) sol-=8;
return sol;
}

int modul(int x) {if (x<0) return -x; return x;}

void submerge_heap(long int heaplen)
{
NOD aux;
long int i=1,min=-1;
while (2*i<=heaplen)
	{
	min=i;
	if (heap[min].cost>heap[2*i].cost&&2*i<=heaplen) min=2*i;
	if (heap[min].cost>heap[2*i+1].cost&&2*i+1<=heaplen) min=2*i+1;
	if (min!=i)
		{
		aux=heap[i];heap[i]=heap[min];heap[min]=aux;
		i=min;
		}
	else break;
	}
}

void rise_heap(long int heaplen)
{
NOD aux;
long int i=heaplen;
while (i!=1&&heap[i/2].cost>heap[i].cost)
	{aux=heap[i/2];heap[i/2]=heap[i];heap[i]=aux;i/=2;}
}

int bf_cu_heap()
{
long int heaplen=8;int i,deviatie;
NOD nou,rad;
for (i=1;i<=8;i++)
	{heap[i].x=xi;heap[i].y=yi;heap[i].dir=i;heap[i].cost=0;}
while (heaplen)
	{
	//1. se extrage_radacina si se marcheaza ca vizitata
	a[heap[1].x][heap[1].y][heap[1].dir]=(char)1;
	rad=heap[1];
	//daca cumva am dat peste solutie...
	if (rad.x==xf&&rad.y==yf) return rad.cost;
	//2. se reface heapul
	heap[1]=heap[heaplen];
	heaplen--;
	submerge_heap(heaplen);
	//3. se adauga la heap noile versiuni, daca e cazul
	for (deviatie=-3;deviatie<=3;deviatie++)
		{
		nou=rad;
		nou.dir=new_dir(rad.dir,deviatie);
		nou.x+=vx[nou.dir];
		nou.y+=vy[nou.dir];
		nou.cost+=modul(deviatie);
		if (nou.y>0&&nou.y<=m&&nou.x>0&&nou.x<=n&&a[nou.x][nou.y][nou.dir]==(char)0)
			{
			//adauga noul nod la heap
			heaplen++;
			heap[heaplen]=nou;
			rise_heap(heaplen);
			}
		}
	}
return -1;
}

int main()
{
//printf("%d",sizeof(NOD));
citire();
int min=bf_cu_heap();
scrie(min);
return 0;
}