Cod sursa(job #132434)

Utilizator andrei.12Andrei Parvu andrei.12 Data 5 februarie 2008 20:21:46
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include<stdio.h>

#define infinit 0x3f3f3f3f
#define lg 505

const int dx[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
int n, m, px, py, fx, fy, i, j, k, found, rsp[lg][lg][9], end[4], cost, st, nrnod, x, y, xx, yy, p, cst, nrm[lg][lg];
char a[lg][lg], fst[lg][lg][9];
struct ches{
	short x, y, dir;
};
ches d[3][lg*lg];
void find(int x, int y){
	
	rsp[x][y][0] = 1;
	found ++;
	for (int i = 1; i <= 8; i ++){
		xx = x+dx[i];
		yy = y+dy[i];
		if (!rsp[xx][yy][0] && xx > 0 && xx <= n && yy > 0 && yy <= m && !a[xx][yy])
			find(xx, yy);
	}
}
inline int fnd(int a){
	if (a > 8)
		return a-8;
	if (a < 1)
		return 8+a;
	return a;
}
inline int as(int a){
	if (a < 0)
		return -a;
	return a;
}
int main()
{
	freopen("car.in", "rt", stdin);
	freopen("car.out", "wt", stdout);
	
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &px, &py, &fx, &fy);
	for (i = 1; i <= n; i ++)
		for (j = 1; j <= m; j ++)
			scanf("%d", &a[i][j]);
	
	find(px, py);
	
	for (i = 1; i <= 8; i ++){
		end[0] ++;
		d[0][end[0]].x = px, d[0][end[0]].y = py;
		d[0][end[0]].dir = i;
	}
	
	st = 1;
	cost = 0, nrnod = 0;
	while (nrnod < found){
		while (st <= end[0]){
			x = d[0][st].x;
			y = d[0][st].y;
			i = d[0][st].dir;
			/*
			if (x == fx && y == fy){
				printf("%d\n", cost);
				return 0;
			}
			*/
			if (!nrm[x][y])
				nrnod ++, nrm[x][y] = 1;
			
			for (j = i-2; j <= i+2; j ++){
				p = fnd(j);
				xx = x+dx[p];
				yy = y+dy[p];
				cst = as(j-i);
				
				if (!a[xx][yy] && xx > 0 && xx <= n && yy > 0 && yy <= m){
					cst = as(j-i);
					/*
					if (x == 9 && y == 13 && i == 4){
						fprintf(stderr, "suntem in %d si %d directia %d cu costul %d", x, y, i, cost);
						fprintf(stderr, "avem %d si %d  in directia %d cu %d\n", xx, yy, p, cst+cost);
					}
					*/
					if (!fst[xx][yy][p]){
						end[cst] ++;
						fst[xx][yy][p] = 1;
						
						d[cst][end[cst]].x = xx;
						d[cst][end[cst]].y = yy;
						d[cst][end[cst]].dir = p;
						rsp[xx][yy][p] = cst+cost;
						//nrnod ++;
					}
					else
						if (cst+cost < rsp[xx][yy][p]){
							end[cst] ++;
							
							d[cst][end[cst]].x = xx;
							d[cst][end[cst]].y = yy;
							d[cst][end[cst]].dir = p;
							rsp[xx][yy][p] = cst+cost;
						}
				}
			}
			
			st ++;
		}
		
		for (i = 1; i <= 2; i ++)
			for (k = 1; k <= end[i]; k ++){
				d[i-1][k].x = d[i][k].x;
				d[i-1][k].y = d[i][k].y;
				d[i-1][k].dir = d[i][k].dir;
			}
		
		cost ++;
		end[0] = end[1], end[1] = end[2], end[2] = 0;
		st = 1;
	}
	
	int min = infinit;
	for (i = 1; i <= 8; i ++)
		if (rsp[fx][fy][i] < min && fst[fx][fy][i])
			min = rsp[fx][fy][i];
	if (min != infinit)
		printf("%d\n", min);
	else
		printf("-1\n");
	
	return 0;
}