Cod sursa(job #205765)

Utilizator devilkindSavin Tiberiu devilkind Data 2 septembrie 2008 21:28:27
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMAX 512
#define mp make_pair
#define ff first
#define ss second

const int dx[]={-1,-1,-1, 0, 1, 1, 1, 0};
const int dy[]={-1, 0, 1, 1, 1, 0,-1,-1};
const int C[]={0,1,2,100000,100000,1000000,2,1};

int a[NMAX][NMAX];
pair< short int, pair< short int, pair<short int,short int> > > H[NMAX*NMAX*20];
short int din[NMAX][NMAX][8];
short int viz[NMAX][NMAX][8];
int SX,SY,DX,DY;
int n,m,dimh;

inline int cpl(int x)
{
	return (x+4)%8;
}

inline int CST(int s, int d)
{
	if (d<s) swap(d,s);
	return C[d-s];
}

void add( pair<int, pair<int , pair<int,int> > > el)
{
	int i=++dimh;

	H[i]=el;
	for (; (i>1)&&(H[i]<H[i/2]); i/=2 )
		swap(H[i], H[i/2]);
}

void recheap(int nod)
{
	int poz=nod;

	if ( (nod*2<=dimh)&&(H[nod*2]<H[poz]) ) poz=nod*2;
	if ( (nod*2+1<=dimh)&&(H[nod*2+1]<H[poz]) ) poz=nod*2+1;

	if (poz==nod) return;

	swap(H[nod],H[poz]);
	recheap(poz);
}

void extract()
{
	swap(H[1],H[dimh]);
	dimh--;
	if (dimh) recheap(1);
}

int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);

	scanf("%d %d",&n,&m);

	scanf("%d %d %d %d ",&SX,&SY, &DX, &DY);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d ",&a[i][j]);

        dimh=0;
	for (int i=0;i<=7;i++)
        	add( mp( 0, mp( i, mp(SX,SY) ) ) );

	int x,y,d,cst,vx,vy,vd,vcst;

        while (dimh)
	{
		x=H[1].ss.ss.ff;
		y=H[1].ss.ss.ss;
		d=H[1].ss.ff;
		cst=H[1].ff;
		extract();
                if ( (viz[x][y][d])&&(!dimh) ) break;

		while (viz[x][y][d])
                {
                        if (dimh==0) break;                
			x=H[1].ss.ss.ff;
			y=H[1].ss.ss.ss;
			d=H[1].ss.ff;
			cst=H[1].ff;
			extract();
                }

                if (viz[x][y][d]) break;
                if (cst>=100000) break;

		din[x][y][d]=cst;
		viz[x][y][d]=1;

		for (int i=0;i<=7;i++)
		{
			vx=x+dx[i];
			vy=y+dy[i];
			vd=cpl(i);
			vcst=cst+CST( cpl(d),i);
			if ( (vx>n) || (vx==0) || (vy>m) || (vy==0) || (viz[vx][vy][vd]) || (a[vx][vy]==1) || (vcst>=100000) ) continue;
			add( mp( vcst, mp( vd, mp(vx,vy) ) ) );
		}
	}

	int sol=0x3f3f3f3f;
	for (int i=1;i<=7;i++)
                if (din[DX][DY][i]) sol=din[DX][DY][i];
	printf("%d",sol);
	return 0;
}