Cod sursa(job #343510)

Utilizator marinaMarina Horlescu marina Data 26 august 2009 09:07:11
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <stdio.h>
#define INPUT "car.in"
#define OUTPUT "car.out"
#define INF 0x3f3f3f3f

void adauga(int x, int y, int dir, int *queue, int ***viz, int m, int n, int **mat, int &sf)
{
	int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
	int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
	
	int xx = x + dx[dir];
	int yy = y + dy[dir];
	if(xx < 0 || xx >= m || yy < 0 || yy >=n) return;
	if(mat[xx][yy] == 1) return;
	if(viz[dir][xx][yy] == -1)
	{
		viz[dir][xx][yy] = viz[dir][x][y];
		int poz = dir + (yy << 3) + (xx << 12);
		queue[++sf] = poz;
		adauga(xx, yy, dir, queue, viz, m, n, mat, sf);
	}
}

int main()
{

//citire date intrare
	
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	int m, n;
	scanf("%d %d", &m, &n);
	
	int si, sj, fi, fj;
	scanf("%d %d %d %d", &si, &sj, &fi, &fj); --si; --sj; --fi; --fj;
	
	int **mat = new int*[m];
	int i, j;
	for(i = 0; i < m; ++i) mat[i] = new int[n];
	
	for(i = 0; i < m; ++i)
		for(j = 0; j < n; ++j)
			scanf("%d", &mat[i][j]);
	
//solve
		
	int *queue = new int[n*m*8];
	int ***viz = new int**[8];
	for(i = 0; i < 8; ++i) viz[i] = new int*[m];
	for(i = 0; i < 8; ++i)
		for(j = 0; j < m; ++j)
			viz[i][j] = new int[n];
	
	int dir;
	for(i = 0; i < m; ++i)
		for(j = 0; j < n; ++j)
			for(dir = 0; dir < 8; ++dir)
				viz[dir][i][j] = -1;
		
	int sf = -1;
	for(dir = 0; dir < 8; ++dir)
	{
		viz[dir][si][sj] = 0;
		int poz = dir + (sj << 3) + (si << 12);
		queue[++sf] = poz;
		adauga(si, sj, dir, queue, viz, m, n, mat, sf);
	}
	
	int ok = 1;
	int *queue2;
	
	while(sf >= 0)
	{
		queue2 = new int[n*m*8];
		int in = 0;
		int sf2 = -1;
		for(;in <= sf; ++in)
		{
			int poz = queue[in];
			int dir = poz & 7;
			int y = (poz >> 3) & 511;
			int x = poz >> 12;
			if(viz[dir+7 & 7] [x][y]== -1)
			{
				viz[dir+7 & 7][x][y] = viz[dir][x][y] + 1;
				queue2[++sf2] = (dir + 7 & 7) + (y << 3) + (x << 12);
				adauga(x, y, dir+7 & 7, queue2, viz, m, n, mat, sf2);
			}
			if(viz[dir+1 & 7][x][y] == -1)
			{
				viz[dir+1 & 7][x][y] = viz[dir][x][y] + 1;
				queue2[++sf2] = (dir + 1 & 7) + (y << 3) + (x << 12);
				adauga(x, y, dir+1 & 7, queue2, viz, m, n, mat, sf2);
			}
		}
		
		int *temp = queue;
		sf = sf2;
		queue = queue2;
		delete temp;
	}
	
//afis rezultat
	
	int min = INF;
	for(dir = 0; dir < 8; ++dir)
		if(viz[dir][fi][fj] != -1 && viz[dir][fi][fj] < min) min = viz[dir][fi][fj];
	if(min == INF) min = -1;
	printf("%d\n", min);
	
	return 0;
}