Cod sursa(job #1347871)

Utilizator hohoho97Valentin Nita hohoho97 Data 19 februarie 2015 12:18:27
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>

#include <vector>
#include <stack>
#include <queue>
#include <string>

#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

const short inceput = 2;

template <class T>
void bfs(vector<vector<T>>& oras, int x1, int y1)
{
	int n = oras.size();
	int m = oras[0].size();

	queue<pair<int, int>> qu;
	qu.push(make_pair(x1, y1));

	int deltay[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
	int deltax[] = { -1, -1, -1, 0, 1, 1, 1, 0 };

	int cost[8][8] = { { 0, 1, 2, 3, 4, 3, 2, 1 } };
	for (int i = 1, lim = sizeof(deltax) / sizeof(int); i < lim; i++)
	{
		int temp = cost[i - 1][lim - 1];
		for (int j = 0; j < lim - 1; j++)
		{
			cost[i][j + 1] = cost[i - 1][j];
		}
		cost[i][0] = temp;
	}

	int directii[] = { 7, 0, 1, 2, 3, 4, 5, 6 };

	vector<vector<char>> directie(n, vector<char>(m));
	directie[x1][y1] = -1;

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

		for (int i = 0; i < sizeof(deltax) / sizeof(int); i++)
		{
			int newx = x + deltax[i];
			int newy = y + deltay[i];
			try
			{
				if (newx >= 0 && newx < m && newy >= 0 && newy < n)
				{
					if (oras[newx][newy] != 1)
					{
						if (oras[newx][newy] == 0)
						{
							directie[newx][newy] = directii[i];
							if (directie[x][y] == -1)
							{
								oras[newx][newy] = oras[x][y];
							}
							else
							{
								oras[newx][newy] = oras[x][y] + cost[directie[x][y]][directie[newx][newy]];//
							}
							qu.push(make_pair(newx, newy));
						}
						else
						{
							if (oras[newx][newy] > oras[x][y] + cost[directie[x][y]][directii[i]])//
							{
								directie[newx][newy] = directii[i];
								oras[newx][newy] = oras[x][y] + cost[directie[x][y]][directie[newx][newy]];//
								qu.push(make_pair(newx, newy));
							}
						}
					}
				}
			}
			catch (exception e)
			{
				cout << e.what();
			}
		}
	}/*

	 for (auto& linie : oras)
	 {
	 for (auto& casuta : linie)
	 {
	 cout << casuta << ' ';
	 }
	 cout << endl;
	 }*/
}

int main()
{
	ifstream in("car.in");

	int n, m;

	in >> n >> m;

	int x1, y1, x2, y2;

	in >> x1 >> y1 >> x2 >> y2;

	vector<vector<short>> oras(n, vector<short>(m));
	for (auto& linie : oras)
	{
		for (auto& casuta : linie)
		{
			in >> casuta;
		}
	}

	oras[x1 - 1][y1 - 1] = inceput;

	in.close();

	bfs(oras, x1 - 1, y1 - 1);

	ofstream out("car.out");

	if (oras[x2 - 1][y2 - 1] == 0)
	{
		out << -1;
	}
	else
	{
		out << oras[x2 - 1][y2 - 1] - inceput;
	}

	out.close();

	return 0;
}