Cod sursa(job #990798)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 29 august 2013 00:58:53
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 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 used[MAXN][MAXN][8];

int minCost = INF;

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

queue<Car> Q[3];

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, 0));
		dist[Si][Sj][i] = 0;
		used[Si][Sj][i] = 1;
	}

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

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


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

			for(int i = -2; i <= 2; 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);

					if(used[newX][newY][newDir] == 0)
					{
						used[newX][newY][newDir] = 1;
						Q[(k+abs(i))%3].push(Car(newX, newY, newDir, dist[newX][newY][newDir]));
					}
				}
			}
		}
		k++;
	}

}

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

	fin >> N >> M;
	fin >> Si >> Sj;
	fin >> Fi >> Fj;

	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++)
		{
			fin >> A[i][j];
		}
	}
	fin.close();

	Dijkstra();

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