Cod sursa(job #505549)

Utilizator cristiprgPrigoana Cristian cristiprg Data 2 decembrie 2010 21:27:39
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 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,1,4,3}, {3,2, 1,0,1,2,1,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;

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>v(N+2), dist(N+2);
	
	v[1] = 1;
	set<pair<int, pair<int, int> > > S; //dist, dir, nod
	S.insert(mp(0, mp(0, 1)));//bag nodu 1 cu dist 0
	while (!S.empty())
	{
	
		d = S.begin()->second.first;
		i = S.begin()->second.second;
		S.erase(S.begin());
		printf("i=%d\n", i);
		for (IT it = G[i].begin(); it != G[i].end(); ++it)
			if (!v[it->first])
			{
				
				costul = cost[d][it->second];
				printf(" - vecin %d cost %d\n", it->first, costul);
				if (costul + dist[i]  < dist[it->first])
					costul = dist[it->first], S.insert(mp(dist[it->first],mp(d, it->second)));
			}
	}
	FILE *f = fopen("car.out", "w");
	fprintf(f, "%d", dist[end_nod]);
}

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