Cod sursa(job #505571)

Utilizator cristiprgPrigoana Cristian cristiprg Data 2 decembrie 2010 22:23:18
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#define DIM 512
#define IT vector< pair<int, int> >::iterator
#define pb push_back 
#define mp make_pair
using namespace std;
const int INF = (1<<30)-2;
const int cost[8][8]={{4,3,2,1,0,1,2,3},{1,4,3,2,1,0,1,2}, {2,1,4,3,2,1,0,1}, {1,2,1,4,3,2,1,0},
					   {0, 1,2,1,4,3,2,1}, {1,0,1,2,1,4,3,2}, {2, 1,0,1,2,3,4,3}, {3,2, 1,0,1,2,3,4}};
const int vi[] = {-1, -1, 0, 1, 1, 1, 0, -1}, vj[] = {0, 1, 1, 1,0, -1, -1, -1};
int n, m, istart, jstart, ifinal, jfinal, a[DIM][DIM], N, end_nod;

inline int abs(int x)
{
	return x<0?-x:x;
}

void read()
{
	FILE *f = fopen("car.in", "r");
	fscanf(f, "%d%d%d%d%d%d", &n, &m, &istart, &jstart, &ifinal, &jfinal);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			fscanf(f, "%d", &a[i][j]);
			if (a[i][j] == 1)
				a[i][j] *= -1;
			
		}
	fclose(f);
}

void afis()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			printf("%3d", a[i][j]);
		printf("\n");
	}
}

bool OK(int i, int j)
{
	if (i < 1 || i > n || j < 1 || j > m)
		return false;
	if (a[i][j] < 0)
		return false;
	return true;
}

void construct_graph(vector< pair<int,int> > G[])
{
	queue<pair<int, int> >Q;
	bitset<DIM*DIM>in_queue;
	in_queue.set(false);
	Q.push(mp(istart, jstart));
	a[istart][jstart] = ++N;
	in_queue[ a[istart][jstart] ] = true;
	int i,j,im, jm;
	
	while (!Q.empty())
	{
		i = Q.front().first;
		j = Q.front().second;
		Q.pop();

		for (int d = 0 ; d < 8; ++d)
		{
			im = i + vi[d];
			jm = j + vj[d];
			if (OK(im, jm))
			{
				
				if (a[im][jm] == 0)
					a[im][jm] = ++N;
				G[a[i][j]].pb(mp(a[im][jm],d));
				
				if (!in_queue[ a[im][jm] ])
				{					
					Q.push(mp(im, jm));
					in_queue[ a[im][jm] ] = true;
					if (im == ifinal && jm == jfinal)
						end_nod = a[im][jm];
				}
				
			}
		}
	}
/*
	afis();
	printf("||---------||\n");
	for (int i = 1; i <= N; ++i )
	{
		printf("%d: ", i);
		for (IT it = G[i].begin() ; it != G[i].end(); ++it)
			printf("%3d (%3d)", it->first, it->second);
		printf("\n");
	}
*/
}

void solve()
{
	vector<pair<int, int> > G[DIM];
	construct_graph(G );
	int i, d, costul;
	vector<int>dist(N+2);
	for (int i = 1; i <= N; ++i)	dist[i] = INF;
	
	multiset<pair<int, pair<int, int> > > S; //dist, dir, nod
	dist[1] = 0;
	for (IT it =G[1].begin(); it != G[1].end(); ++it)
		S.insert(mp(0, mp(it->second, it->first))), dist[it->first] = 0;
	
	while (!S.empty())
	{
	
		d = S.begin()->second.first;
		i = S.begin()->second.second;
		
		S.erase(*S.begin());
	//	printf("d = %d i = %d\n", d, i);
		for (IT it = G[i].begin(); it != G[i].end(); ++it)
			if (it->first != 1)
			{
				
				costul = cost[(4+d)%8][it->second];
				//printf(" - vecin %d dir = %d cost = %d\n",it->first, it->second, costul);
				if (costul + dist[i]  < dist[it->first])
					dist[it->first] = costul + dist[i], S.insert(mp(dist[it->first],mp(it->second, it->first))); //printf("intrat\n");
			}
	}
	FILE *f = fopen("car.out", "w");
	fprintf(f, "%d", dist[end_nod]);
}

int main()
{
	read();
	solve();
	
	return 0;
}