Cod sursa(job #3216627)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 18 martie 2024 19:51:43
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <string.h>

int n, m;

int a[510][510];

int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1};
int dy[] = { 0, 1, 1, 1, 0,-1,-1,-1};

int cur[2000010];
int urm[2000010];

char viz[8][510][510];

int main()
{
	int i, j, pc, qc, pu, qu, x, y, xb, yb, xf, yf, dir;

	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);

	scanf("%d %d", &n, &m);

	scanf("%d %d %d %d", &xb, &yb, &xf, &yf);

	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);

	for (i = 0; i <= n+1; i++)
	{
		a[i][0] = 1;
		a[i][m+1] = 1;
	}
	for (j = 0; j <= m+1; j++)
	{
		a[0][j] = 1;
		a[n+1][j] = 1;
	}
	

	for (i = 0; i < 8; i++)
	{
		cur[i] = xb + (yb << 9) + (i << 18);
		viz[i][xb][yb] = 1;
	}

	pc = 0;
	qc = 7;

	pu = 0;
	qu = -1;

	int cost = 0;
	int e = 0;

	while (1)
	{
		//expandez cur pana nu mai pot

		while (pc <= qc)
		{
			x = cur[pc] & 511;
			y = (cur[pc] >> 9) & 511;

			if (x == xf && y == yf)
			{
				e = 1;
				break;
			}
			dir = cur[pc] >> 18;
			
			// acu mut una in directie

			if (!viz[dir][x + dx[dir]][y + dy[dir]] && !a[x + dx[dir]][y + dy[dir]])
			{
				cur[++qc] = x + dx[dir] + ((y + dy[dir]) << 9) + (dir << 18);
				viz[dir][x + dx[dir]][y + dy[dir]] = 1;
			}

			pc++;
		}

		for (i = 0; i <= qc; i++)
		{
			x = cur[i] & 511;
			y = (cur[i] >> 9) & 511;
			dir = cur[i] >> 18;

			// il mut cu o directie in plus
			if (!viz[(dir + 1) & 7][x][y])
			{
				urm[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);
				viz[(dir + 1) & 7][x][y] = 1;
			}

			//il mut cu o directie in minus
			dir--;
			if (dir < 0) dir = 7;

			if (!viz[dir][x][y])
			{
				urm[++qu] = x + (y << 9) + (dir << 18);
				viz[dir][x][y] = 1;
			}			
		}

		if (e) break;
		if (qu == -1) 
		{

			cost = -1;
			break;
		}

		cost ++;

		memcpy(cur, urm, sizeof(cur));

		pc = 0;
		qc = qu;
		qu = -1;
	}

	printf("%d\n", cost);


fclose(stdin);
fclose(stdout);
return 0;
}