Cod sursa(job #634951)

Utilizator informatician28Andrei Dinu informatician28 Data 17 noiembrie 2011 23:37:14
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream> 
#include<queue> 
#include<cmath>
using namespace std; 
ifstream in("car.in"); 
ofstream out("car.out"); 
int N,M,Si,Sj,Fi,Fj,cost=0, a[501][501],costfinal;
int const dx[]={-1,-1,-1,0,0,1,1,1}, dy[]={-1,0,1,-1,1,-1,0,1};
queue<int>c;

void Read() 
{ 
	in>>N>>M; 
	in>>Si>>Sj>>Fi>>Fj; 
	for(int i=1;i<=N;i++) 
		for(int j=1;j<=M;j++) 
			in>>a[i][j];
}
void Bfs()
{
	int i,j,lin,col;
	c.push(Si); 
	c.push(Sj); 
	while(!c.empty()) 
	{
		i=c.front(); 
		c.pop(); 
		j=c.front(); 
		c.pop(); 
		for(int dir=0;dir<8;dir++) 
			{
				if(a[i+dx[dir]][j+dy[dir]]==0 && a[i][j]!=a[Si][Sj])
			{
				lin=i+dx[dir];				
				col=j+dy[dir];
                c.push(lin); 
                c.push(col); 
                if(abs(i-lin)!=0) 
                cost+=abs(i-lin); 
		        if(abs(j-col)!=0) 
			    cost+=abs(j-col); 
				if(lin==Fi && col==Fj) 
					costfinal=cost;
			}
			else if(a[i+dx[dir]][j+dy[dir]]==0 && a[i][j]==a[Si][Sj]) 
			{ 
                lin=i+dx[dir]; 
                col=j+dy[dir]; 
                c.push(lin); 
				c.push(col); 
			}
		}
	}
}
				
int main() 
{
	Read();
	Bfs();
	out<<costfinal; 
}