Cod sursa(job #383586)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 16 ianuarie 2010 23:47:58
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<cstdio>
#define N 501
#define minn(a,b) ((a<b) ? (a):(b))
bool a[N][N],viz[5][N][N],nod[N][N];
short int coada[5][N*N][2],dir[5][N*N],x1[2],y1[2],nr_nod,nr,n,m;
int u[5],p[5],cost[9][9],dist[5][N][N],minim=(1<<31)-1;
const int dx[]={0,0,-1,1,-1,-1,1,1};
const int dy[]={1,-1,0,0,-1,1,-1,1};
void citire()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%hd%hd%hd%hd%hd%hd",&n,&m,&x1[0],&x1[1],&y1[0],&y1[1]);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j)
		{
			scanf("%hd",&a[i][j]);
			if (a[i][j])
				a[i][j]=0;
			else
			{
				a[i][j]=1;
				++nr_nod;
			}
		}
}
void costuri()
{
	for (int i=0; i<=8; ++i)
		cost[i][i]=0;
	cost[0][5]=cost[0][7]=cost[5][0]=cost[7][0]=cost[1][4]=cost[1][6]=cost[6][1]=cost[4][1]=cost[2][4]=cost[4][2]=cost[2][5]=cost[5][2]=cost[3][6]=cost[6][3]=cost[3][7]=cost[7][3]=1;
	cost[0][4]=cost[4][0]=cost[0][6]=cost[6][0]=cost[1][5]=cost[5][1]=cost[1][7]=cost[7][1]=cost[2][6]=cost[6][2]=cost[2][7]=cost[7][2]=cost[3][4]=cost[4][3]=cost[3][5]=cost[5][3]=3;
	cost[0][2]=cost[2][0]=cost[0][3]=cost[3][0]=cost[1][2]=cost[2][1]=cost[1][3]=cost[3][1]=cost[4][5]=cost[5][4]=cost[4][6]=cost[6][4]=cost[7][5]=cost[5][7]=cost[6][7]=cost[7][6]=2;
	cost[0][1]=cost[1][0]=cost[2][3]=cost[3][2]=cost[4][7]=cost[7][4]=cost[5][6]=cost[6][5];
}
void bfs(short int x0[])
{
	
	short int x[2],y[2];
	nod[x0[0]][x0[1]]=true;
	++nr;
	bool ok=true;
	coada[0][u[0]][0]=x0[0];
	coada[0][u[0]][1]=x0[1];
	dir[0][u[0]++]=8;
	viz[0][x0[0]][x0[1]]=true;
	while (nr<nr_nod)
	{
		for (int i=0; i<=4; ++i)
		{
			ok=false;
			while (u[i]!=p[i])
			{
				ok=true;
				x[0]=coada[i][p[i]][0];
				x[1]=coada[i][p[i]][1];
				int d=dir[i][p[i]++];
				for (int j=0; j<=7; ++j)
				{
					y[0]=x[0]+dx[j];
					y[1]=x[1]+dy[j];
					if (!a[y[0]][y[1]])
						continue;
					int q=(cost[d][j]+i)%4;
					if (viz[q][y[0]][y[1]])
						continue;
					coada[q][u[q]][0]=y[0];
					coada[q][u[q]][1]=y[1];
					viz[q][y[0]][y[1]]=true;
					dir[q][u[q]++]=j;
					dist[q][y[0]][y[1]]=cost[d][j]+dist[i][x[0]][x[1]];
					if (nod[y[0]][y[1]])
						continue;
					++nr;
					nod[y[0]][y[1]]=true;
				}
			}
		}
	}
	
}
void afis()
{
	for (int i=0; i<=4; ++i)
		if (viz[i][y1[0]][y1[1]])
			minim=minn(minim,dist[i][y1[0]][y1[1]]);
	printf("%d",minim);
}
int main()
{
	citire();
	costuri();
	bfs(x1);
	afis();
	return 0;
}