Cod sursa(job #990849)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 29 august 2013 03:16:28
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "car";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;

int N, M;
int Si, Sj;
int Fi, Fj;

#define MAXN 501

int A[MAXN][MAXN];
int dist[MAXN][MAXN][8];

int minCost = INF;


struct Car
{
	int x;
	int y;
	int dir;
	int dis;
	Car(int x, int y, int dir)
	{
		this->x = x;
		this->y = y;
		this->dir = dir;
	}
};

queue<Car> Q[2];

int dY[] = {0, 1 ,1 ,1, 0, -1, -1, -1};
int dX[] = {-1, -1, 0, 1, 1, 1, 0, -1};

void Dijkstra()
{
	int k = 0;
	for(int i = 0; i < 8; i++)
	{
		Q[0].push(Car(Si, Sj, i));
		dist[Si][Sj][i] = 0;
	}

	while(true)
	{
		if(minCost != INF)
			break;
		if(Q[0].empty() == true && Q[1].empty() == true)
			break;

		while(Q[k%2].empty() == false)
		{
			Car c = Q[k%2].front();
			Q[k%2].pop();

			if(c.x == Fi && c.y == Fj)
			{
				minCost = min(minCost, dist[c.x][c.y][c.dir]);
			}		

			for(int i = -1; i <= 1; i += 2)
			{
				int newDir = (c.dir + i) % 8;
				newDir = newDir < 0 ? newDir + 8 : newDir;

				if(dist[c.x][c.y][newDir] > dist[c.x][c.y][c.dir] + abs(i))
				{
					dist[c.x][c.y][newDir] = dist[c.x][c.y][c.dir] + abs(i);
					Q[(k+abs(i))%2].push(Car(c.x, c.y, newDir));
				}
			}

			for(int i = -1; i <= 1; i++)
			{
				int newDir = (c.dir + i) % 8;
				newDir = newDir < 0 ? newDir + 8 : newDir;

				int newX = c.x + dX[newDir];
				int newY = c.y + dY[newDir];

				if(!( 1 <= newX && newX <= N && 1<= newY && newY <= M)) 
					continue;

				if(A[newX][newY] == 1)
					continue;

				if(dist[newX][newY][newDir] > dist[c.x][c.y][c.dir] + abs(i))
				{
					dist[newX][newY][newDir] = dist[c.x][c.y][c.dir] + abs(i);
					Q[(k+abs(i))%2].push(Car(newX, newY, newDir));
				}
			}
		}
		k++;
	}

}


fstream fin(infile.c_str(), ios::in);

const int BUFLEN = 4084;
char buffer[BUFLEN];
int p;


int nextInt()
{
	int result = 0;
	while(!( '0' <=buffer[p] && buffer[p] <= '9'))
	{
		if(++p >= BUFLEN)
		{
			fin.read(buffer, BUFLEN);
			p = 0;
		}
	}
	
	while( '0' <=buffer[p] && buffer[p] <= '9')
	{
		result *= 10;
		result += buffer[p] - '0';
		if(++p >= BUFLEN)
		{
			fin.read(buffer, BUFLEN);
			p = 0;
		}
	}
	return result;
}

int main()
{
	p = BUFLEN;
	N = nextInt();
	M = nextInt();
	Si = nextInt();
	Sj = nextInt();
	Fi = nextInt();
	Fj = nextInt();

	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= M; j++)
		{
			for(int k = 0; k < 8; k++)
			{
				dist[i][j][k] = INF;
			}
		}
	}

	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= M; j++)
		{
			A[i][j] = nextInt();
		}
	}
	fin.close();

	Dijkstra();

	fstream fout(outfile.c_str(), ios::out);
	if(minCost != INF)
	{
		fout << minCost << "\n";
	}
	else 
	{
		fout << "-1\n";
	}
	fout.close();
}