Cod sursa(job #75429)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 1 august 2007 19:45:48
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXN=500;//500
const long int MAXDIR=8;
const long int vi[9]={0,-1,-1,0,1,1,1,0,-1};
const long int vj[9]={0,0,1,1,1,0,-1,-1,-1};
const long int cost[5]={0,1,2,3,4}; 
long int map[MAXN+1][MAXN+1];
long int a[MAXN+1][MAXN+1][MAXDIR+1];
long int heaplen,n,m,ii,ji,il,jl;
typedef struct NOD {long int i,j,dir;};
NOD heap[MAXN*MAXN*MAXDIR+1];

///////////////////////////
// INPUT
///////////////////////////

void init()
{
long int i;
for (i=1;i<=8;i++)
	{
	a[ii][ji][i]=1;
	heaplen++;
	heap[heaplen].i=ii;
	heap[heaplen].j=ji;
	heap[heaplen].dir=i;
	}
}

void citire()
{
FILE *f=fopen("car.in","r");
fscanf(f,"%ld%ld",&n,&m);
fscanf(f,"%ld%ld%ld%ld",&ii,&ji,&il,&jl);
long int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
	fscanf(f,"%ld",&map[i][j]);
fclose(f);
}

////////////////////////////
// HEAP HANDLING
////////////////////////////

void submerge_heap(long int i)
{
long int m=i;NOD aux;
for (;;)
	{
	if (2*i<=heaplen&&a[heap[2*i].i][heap[2*i].j][heap[2*i].dir]<a[heap[m].i][heap[m].j][heap[m].dir]) m=2*i;
	if (2*i+1<=heaplen&&a[heap[2*i+1].i][heap[2*i+1].j][heap[2*i+1].dir]<a[heap[m].i][heap[m].j][heap[m].dir]) m=2*i+1;
	if (m==i) break;
	aux=heap[i];heap[i]=heap[m];heap[m]=aux;
	i=m;
	}
}

void float_heap(long int i)
{
long int m=i/2;
NOD aux;
while (m&&a[heap[m].i][heap[m].j][heap[m].dir]>a[heap[i].i][heap[i].j][heap[i].dir])
	{
	aux=heap[i];heap[i]=heap[m];heap[m]=aux;
	i=m;
	m=i/2;
	}
}

/////////////////////////////
// NOD Handlers  && other handlers
/////////////////////////////

void update(NOD &a) {a.i+=vi[a.dir];a.j+=vj[a.dir];}
int valid(NOD aa)
{
if (aa.i<=0||aa.j<=0) return 0;
if (aa.i>n||aa.j>m) return 0;
if (map[aa.i][aa.j]) return 0;
if (a[aa.i][aa.j][aa.dir]) return 0;
return 1;
}
long int normalize_8(long int a) {if (a>8) return a-8;if (a<=0) return a+8; return a;}
long int get_a(NOD x) {return a[x.i][x.j][x.dir];}
void set_a(NOD x, long int val) {a[x.i][x.j][x.dir]=val;}
long int is_solution(NOD a) {if (a.i==il&&a.j==jl) return 1; return 0;}


/////////////////////////////
// FLOOD FILL
/////////////////////////////

long int bf()
{
NOD crt,nou,now,aux2;
long int nd;
while (heaplen)
	{
	crt=heap[1];
	nou=crt;
	heap[1]=heap[heaplen];
	heaplen--;
	submerge_heap(1);
	update(crt);
	while (valid(crt))
		{
		for (nd=0;nd<=3;nd++)
			{
			now=crt;now.dir=normalize_8(crt.dir+nd);
			aux2=now;update(aux2);
			if (is_solution(now)) return get_a(nou)-1;
			if (!get_a(now)&&valid(aux2))
				{
				set_a(now,cost[nd]+get_a(nou));
				if (nd!=0)
					{
					heap[++heaplen]=now;
					float_heap(heaplen);
					}
				}
			now=crt;now.dir=normalize_8(crt.dir-nd);
			aux2=now;update(aux2);
			if (is_solution(now)) return get_a(nou)-1;
			if (!get_a(now)&&valid(aux2))
				{
				set_a(now,cost[nd]+get_a(nou));
				if (nd!=0)
					{
					heap[++heaplen]=now;
					float_heap(heaplen);
					}
				}
			}
		update(crt);
		}
	}
return -1;
}

/////////////////////////////
// MAIN
/////////////////////////////

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

int main()
{
citire();
init();
long int sol=bf();
scrie(sol);
return 0;
}