Cod sursa(job #72744)

Utilizator scapryConstantin Berzan scapry Data 15 iulie 2007 12:59:44
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <stdio.h>
#include <list>
using namespace std;

enum { maxsize = 502, dirs = 8 };
const int dir[dirs][2] = //clockwise
{
	{ -1, -1 },
	{ -1,  0 },
	{ -1,  1 },
	{  0,  1 },
	{  1,  1 },
	{  1,  0 },
	{  1, -1 },
	{  0, -1 }
};
const int next[dirs] = { 1, 2, 3, 4, 5, 6, 7, 0 },
          prev[dirs] = { 7, 0, 1, 2, 3, 4, 5, 6 };

int rows, cols;
int sr, sc, er, ec;
bool bad[maxsize][maxsize];
int reached[maxsize][maxsize][dirs]; //cost we reached that node with

list<int> node[2]; //node[cost % 2] is of cost cost; node[(cost + 1) % 2] is of cost cost+1;

int ans;

//int adds;

inline int compress(int r, int c, int d)
{
	return ((r * maxsize) + c) * dirs + d;
}

inline void decompress(int node, int &r, int &c, int &d)
{
	d = node % dirs;
	node /= dirs;

	r = node / maxsize;
	c = node % maxsize;
}

inline void add_nocheck(int cost, int r, int c, int d)
{
	if(reached[r][c][d] > cost)
	{
		/*
		if(reached[r][c][d] != 0x3f3f3f3f)
			printf("r %d c %d d %d disgust (old %d now %d)\n",
					r, c, d, reached[r][c][d], cost);
		*/

		reached[r][c][d] = cost;

		node[cost % 2].push_back(compress(r, c, d));
		//adds++;
	}
}

/**
 * adds only if r and c are valid
 */
inline void attempt_add(int cost, int r, int c, int d)
{
	if(r >= 0 && r < rows && c >= 0 && c < cols)
		if(!bad[r][c])
			add_nocheck(cost, r, c, d);
}

void go()
{
	int i, tmp, r, c, d;
	int cost = 0;

	memset(reached, 0x3f, sizeof(reached));

	if(!bad[sr][sc])
	{
		for(i = 0; i < dirs; i++)
			add_nocheck(0, sr, sc, i);
	}

	while(!node[0].empty() || !node[1].empty())
	{
		if(node[cost % 2].empty())
			cost++;

		tmp = *(node[cost % 2].begin());
		node[cost % 2].pop_front();
		decompress(tmp, r, c, d);

		if(r == er && c == ec)
			break; //ans is current cost

		if(cost > reached[r][c][d]) //stale node, don't bother
			continue;

		//straight (cost 0)
		attempt_add(cost, r + dir[d][0], c + dir[d][1], d);

		//previous dir (45 deg ccw) (cost 1)
		add_nocheck(cost + 1, r, c, prev[d]);

		//next dir (45 deg cw) (cost 1)
		add_nocheck(cost + 1, r, c, next[d]);
	}

	if(node[0].empty() && node[1].empty()) //didn't reach end
		ans = -1;
	else
		ans = cost;

	//printf("%d adds\n", adds);
}

int main()
{
	int i, j, tmp;
	FILE *f = fopen("car.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &rows, &cols);
	fscanf(f, "%d%d%d%d", &sr, &sc, &er, &ec);
	sr--; sc--;
	er--; ec--;

	for(i = 0; i < rows; i++)
		for(j = 0; j < cols; j++)
		{
			fscanf(f, "%d", &tmp);
			bad[i][j] = tmp;
		}

	fclose(f);
	f = fopen("car.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}