Cod sursa(job #1393665)

Utilizator theprdvtheprdv theprdv Data 19 martie 2015 17:43:39
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

fstream fin("car.in", ios::in);
fstream fout("car.out", ios::out);

#define MAXDIM 510
int m, n, map[MAXDIM][MAXDIM], minn = 250000;
queue <pair<int, pair<int, int>>> q;
pair<int, int> final;
bool first = true, used[MAXDIM][MAXDIM];

void read()
{
	int x, y, w, z;
	fin >> n >> m;
	fin >> x >> y >> w >> z;
	q.push(make_pair(x, make_pair(y, 0)));
	final = make_pair(w, z);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			fin >> x,
			map[i][j] = x;
	fin.close();
}
void neighbour(int old_cost, int next_i, int next_j, int way )
{
	if (next_i > n || next_i < 1 || next_j > m || next_j < 1 || map[next_i][next_j] != 0) return;
	int dif = abs(q.front().second.second - way), cost, next_way =  way < 5 ? way + 4 : way - 4;
	if (first) cost = 0;
	else cost = dif == 4 ? 0 : dif == 3 || dif == 5 ? 1 : dif == 6 || dif == 2 ? 2 : dif == 1 || dif == 7 ? 3 : 4;
	if ((map[next_i][next_j] > cost + old_cost || used[next_i][next_j] == false) && dif != 0)
		q.push(make_pair(next_i, make_pair(next_j, next_way))),
		map[next_i][next_j] = old_cost + cost,
		used[next_i][next_j] = true;
}
void LEE()
{
	int i, j, way, next_i, next_j;
	used[q.front().first][q.front().second.first] = true;
	while (!q.empty()){
		i = q.front().first, j = q.front().second.first, way = q.front().second.second;
		for (int k = 1; k <= 8; k++){
			k < 4 ? next_i = -1 : k > 4 && k < 8 ? next_i = 1 : next_i = 0;
			k > 6 || k == 1 ? next_j = -1 : k > 2 && k < 6 ? next_j = 1 : next_j = 0;
			neighbour(map[i][j], i + next_i, j + next_j, k);
		}
		if (i == final.first && j == final.second && map[i][j] < minn) 
			minn = map[i][j];
		q.pop();
		first = false;
	}
}

int main()
{
	read();
	LEE();
	if (minn == 250000) fout << -1;
	else fout << minn;

	fout.close();
	return 0;
}