Cod sursa(job #731299)

Utilizator eukristianCristian L. eukristian Data 7 aprilie 2012 21:13:14
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdio>
#include <queue>
using std::queue;

#define MAXN 500
#define dirMask 7
#define yMask 4088

bool mat[MAXN][MAXN], vis[MAXN][MAXN][8];

const int delta[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
int dist[MAXN][MAXN][8];
queue<int> Q[2];

int sx, sy, fx, fy, n, m, result;

inline int getCode(int x, int y, int dir)
{
	return (x << 12) + (y << 3) + dir;
}

inline bool withinBounds(int x, int y)
{
	return x >= 0 && x < n && y >= 0 && y < m;
}

inline void relax(int state, int crtList)
{
	int x = state >> 12;
	int y = (state & yMask) >> 3;
	int dir = state & dirMask;

	if (x == fx && y == fy)
	{
		result = dist[x][y][dir] + 1;
		return;
	}

	int crtDir = dir;
	int newX = x + delta[crtDir][0], newY = y + delta[crtDir][1];
	if (withinBounds(newX, newY) && mat[newX][newY] == 0 && (!vis[newX][newY][crtDir] || dist[newX][newY][crtDir] > dist[x][y][dir]))
	{
		vis[newX][newY][crtDir] = true;
		dist[newX][newY][crtDir] = dist[x][y][dir];
		Q[crtList].push(getCode(newX, newY, crtDir));
	}

	crtDir = dir + 1 > 7 ? 0 : dir + 1;
	if (!vis[x][y][crtDir] || dist[x][y][crtDir] > dist[x][y][dir] + 1)
	{
		vis[x][y][crtDir] = true;
		dist[x][y][crtDir] = dist[x][y][dir] + 1;
		Q[1 - crtList].push(getCode(x, y, crtDir));
	}

	crtDir = dir - 1 < 0 ? 7 : dir - 1;
	if (!vis[x][y][crtDir] || dist[x][y][crtDir] > dist[x][y][dir] + 1)
	{
		vis[x][y][crtDir] = true;
		dist[x][y][crtDir] = dist[x][y][dir] + 1;
		Q[1 - crtList].push(getCode(x, y, crtDir));
	}
}

int main()
{
	freopen("car.in", "r", stdin);
	freopen("car.out","w",stdout);
	scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &fx, &fy);

	sx--;sy--;fx--;fy--;

	for (int i = 0 ; i < n ; ++i)
		for (int j = 0 ; j < m ; ++j)
			scanf("%d", &mat[i][j]);

	for (int i = 0 ; i < 8 ; ++i)
	{
		vis[sx][sy][i] = true;
		Q[0].push(getCode(sx, sy, i));
	}

	int current_cost = 0, pos = 0, crt = 0;

	while ((!Q[0].empty() || !Q[1].empty()) && result < 1)
	{
		while (!Q[crt].empty() && result < 1)
		{
			int crtElem = Q[crt].front();
			Q[crt].pop();
			relax(crtElem, crt);
		}

		crt = 1 - crt;
	}

	printf("%d\n", result - 1);

	return 0;
}