Cod sursa(job #132291)

Utilizator andrei.12Andrei Parvu andrei.12 Data 5 februarie 2008 16:02:06
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 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], end[4], cost, st, nrnod, x, y, xx, yy, p, cst;
char a[lg][lg], fst[lg][lg];
struct ches{
	short x, y;
};
ches d[3][lg*lg][9];
void find(int x, int y){
	
	rsp[x][y] = infinit;
	found ++;
	for (int i = 1; i <= 8; i ++){
		xx = x+dx[i];
		yy = y+dy[i];
		if (!rsp[xx][yy] && xx > 0 && xx <= n && yy > 0 && yy <= m)
			find(xx, yy);
	}
}
int fnd(int a){
	if (a > 8)
		return a-8;
	if (a < 1)
		return 8+a;
	return a;
}
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 ++)
		d[0][1][i].x = px, d[0][1][i].y = py;
	
	end[0] = 1, st = 1;
	cost = 0, nrnod = 1;
	while (nrnod <= found){
		while (st <= end[0]){
			for (i = 1; i <= 8; i ++){
				x = d[0][st][i].x;
				y = d[0][st][i].y;
				
				if (x == fx && y == fy){
					printf("%d\n", cost);
					return 0;
				}
				
				for (j = i-2; j <= i+2; j ++){
					p = fnd(j);
					xx = x+dx[p];
					yy = y+dy[p];
					
					if (!a[xx][yy] && xx > 0 && xx <= n && yy > 0 && yy <= m){
						cst = as(j-i);
						
						if (!fst[xx][yy]){
							end[cst] ++;
							fst[xx][yy] = 1;
							
							d[cst][end[cst]][p].x = xx;
							d[cst][end[cst]][p].y = yy;
							rsp[xx][yy] = cst+cost;
							nrnod ++;
						}
						else
							if (cst+cost < rsp[xx][yy]){
								end[cst] ++;
								
								d[cst][end[cst]][p].x = xx;
								d[cst][end[cst]][p].y = yy;
								rsp[xx][yy] = cst+cost;
							}
					}
				}
			}
			
			st ++;
		}
		
		for (i = 1; i <= 2; i ++)
			for (k = 1; k <= end[i]; k ++)
				for (j = 1; j <= 8; j ++){
					d[i-1][k][j].x = d[i][k][j].x;
					d[i-1][k][j].y = d[i][k][j].y;
				}
		
		cost ++;
		end[0] = end[1], end[1] = end[2], end[2] = 0;
		st = 1;
	}
	
	printf("-1\n");
	
	return 0;
}