Cod sursa(job #1047222)

Utilizator rvnzphrvnzph rvnzph Data 4 decembrie 2013 01:19:00
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <queue>

using namespace std;

const int NLen=500;
const int MLen=500;

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};

int v[NLen][MLen];

int diff(int x,int y)
{
	if(x<y) return y-x;
	return x-y;
}

//use 2 queues
//one contains the pair of the coordinates of the current position
//the other contains the pair of the coordinates of the position we came from

queue <pair<int,int> > at,from;

int getCost(int ax,int ay,int x,int y,int bx,int by)
{
	int dx=x-ax;
	int dy=y-ay;

	//printf("%d %d :: %d %d :: %d %d :: %d\n",ax,ay,x,y,bx,by,diff(x+dx,bx)+diff(y+dy,by));
	return diff(x+dx,bx)+diff(y+dy,by);
}

int bfs(int N,int M,int Si,int Sj,int Fi,int Fj)
{
	//initialize queues
	for(int i=0;i<8;++i)
	{
		at.push(make_pair(Si,Sj));
		from.push(make_pair(Si+dx[i],Sj+dy[i]));
	}
	v[Si][Sj]=0;

	while(!at.empty())
	{
		int x=at.front().first;
		int y=at.front().second;

		int px=from.front().first;
		int py=from.front().second;

		//printf("%d, %d  >  %d, %d\n",px,py,x,y);
		/*
		for(int i=0;i<N;++i)
		{
			for(int j=0;j<M;++j)
				printf("%d ",v[i][j]);
			printf("\n");
		}
		*/

		at.pop();
		from.pop();

		for(int i=0;i<8;++i)
			if(0<=x+dx[i]&&x+dx[i]<N&&
				0<=y+dy[i]&&y+dy[i]<M)
				if(v[x+dx[i]][y+dy[i]]!=-1)
				{
					int val=getCost(px,py,x,y,x+dx[i],y+dy[i]);
					//if(val>2) continue;
					if(v[x+dx[i]][y+dy[i]]==-2||v[x+dx[i]][y+dy[i]]>v[x][y]+val)
					{
						v[x+dx[i]][y+dy[i]]=v[x][y]+val;
						at.push(make_pair(x+dx[i],y+dy[i]));
						from.push(make_pair(x,y));
					}
				}
	}

	return v[Fi][Fj];
}

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

	int N,M;
	scanf("%d%d",&N,&M);

	int Si,Sj,Fi,Fj;
	scanf("%d%d%d%d",&Si,&Sj,&Fi,&Fj);

	for(int i=0;i<N;++i)
		for(int j=0;j<M;++j)
		{
			scanf("%d",&v[i][j]);
			v[i][j]-=2;
		}

	printf("%d\n",bfs(N,M,Si-1,Sj-1,Fi-1,Fj-1));

	return 0;
}