Cod sursa(job #990847)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 29 august 2013 03:11:41
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.02 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 Nod
{
	int lista;
	int x;
	int y;
	int dir;
	Nod*next;
	Nod*prev;

	Nod(int x = 0, int y = 0, int dir = 0, int lista = -1)
	{
		this->x = x;
		this->y = y;
		this->lista = lista;
		this->dir = dir;
	}
};

struct Lista
{
	Nod begin;
	int size;
	Lista()
	{
		begin.next = &begin;
		begin.prev = &begin;
		size = 0;
	}

	Nod* popFront()
	{
		if(size == 0)
			return NULL;
		Nod * r = begin.next;
		r->next->prev = r->prev;
		r->prev->next = r->next;
		size--;
		return r;
	}

	void deleteNod(Nod* nod)
	{
		nod->next->prev = nod->prev;
		nod->prev->next = nod->next;
		nod->lista = -1;
		size--;
	}

	void pushBack(Nod* nod)
	{
		nod->next = &begin;
		nod->prev = begin.prev;

		nod->prev->next = nod;
		nod->next->prev = nod;
		size++;
	}
};

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;
	}
};


Lista lists[2];
Nod nods[MAXN][MAXN][8];

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));

		nods[Si][Sj][i].lista = 0;
		lists[0].pushBack(&nods[Si][Sj][i]);

		dist[Si][Sj][i] = 0;
	}

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


		if(lists[0].size == 0 && lists[1].size == 0)
			break;
		while(lists[k%2].size != 0)
		//while(Q[k%2].empty() == false)
		{
			//Car c = Q[k%2].front();
			//Q[k%2].pop();

			Nod c = *lists[k%2].popFront();

			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));

					if(nods[c.x][c.y][newDir].lista != -1)
						lists[nods[c.x][c.y][newDir].lista].deleteNod(&nods[c.x][c.y][newDir]);
					
					nods[c.x][c.y][newDir].lista = (k + abs(i))%2;
					lists[(k + abs(i))%2].pushBack(&nods[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));

					if(nods[newX][newY][newDir].lista != -1)
						lists[nods[newX][newY][newDir].lista].deleteNod(&nods[newX][newY][newDir]);
					nods[newX][newY][newDir].lista = (k + abs(i))%2;
					lists[(k + abs(i))%2].pushBack(&nods[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++)
			{
				nods[i][j][k] = Nod(i, j, k);
			}
		}
	}


	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();
}