Cod sursa(job #72740)

Utilizator scapryConstantin Berzan scapry Data 15 iulie 2007 12:42:35
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <assert.h>
#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 }
};

int rows, cols;
int sr, sc, er, ec;
bool bad[maxsize][maxsize];
bool v[maxsize][maxsize][dirs];

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

int ans;

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;
}

/**
 * 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] && !v[r][c][d])
		{
			v[r][c][d] = true;
			node[cost % 2].push_back(compress(r, c, d));
		}
}

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

	if(!bad[sr][sc])
	{
		for(i = 0; i < dirs; i++)
			attempt_add(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

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

		//previous dir (45 deg ccw) (cost 1)
		attempt_add(cost + 1, r, c, (d + dirs - 1) % dirs);

		//next dir (45 deg cw) (cost 1)
		attempt_add(cost + 1, r, c, (d + 1) % dirs);
	}

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

int main()
{
	int i, j;
	char shit[maxsize * 2 + 10], *p;
	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++)
	{
		fgets(shit, cols * 2 + 2, f);

		p = shit;
		for(j = 0; j < cols; j++)
		{
			if(*p == '1')
				bad[i][j] = true;
			else
				assert(*p == '0');
			p += 2;
		}
	}

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

	go();

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