Cod sursa(job #213607)

Utilizator madmanjonesJones the one madmanjones Data 10 octombrie 2008 16:21:37
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 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, rsp[lg][lg][9], end[4], cost, st, x, y, xx, yy, p, cst, s;
char a[lg][2000], fst[lg][lg][9];
struct ches{
	short x, y;
	char dir;
};
ches d[3][lg*lg];
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\n", &px, &py, &fx, &fy);
	for (i = 1; i <= n; i ++)
		fgets(a[i], 2000, stdin);
	
	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;
	while (!s){
		while (st <= end[0]){
			x = d[0][st].x;
			y = d[0][st].y;
			i = d[0][st].dir;
			
			for (j = -1; j < 2; j ++)
				if (j != 0){
					p = fnd(i+j);
					
					if (!fst[x][y][p]){
						end[1] ++;
						fst[x][y][p] = 1;
						
						d[1][end[1]].x = x;
						d[1][end[1]].y = y;
						d[1][end[1]].dir = p;
						rsp[x][y][p] = 1+cost;
						//nrnod ++;
					}
					else
						if (1+cost < rsp[x][y][p]){
							end[1] ++;
							
							d[1][end[1]].x = x;
							d[1][end[1]].y = y;
							d[1][end[1]].dir = p;
							rsp[x][y][p] = 1+cost;
						}
				}
			
			for (j = i-1; j <= i+1; j ++){
				p = fnd(j);
				xx = x+dx[p];
				yy = y+dy[p];
				cst = as(j-i);
				
				if (a[xx][2*(yy-1)] == '0' && 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 (k = 1; k <= end[1]; k ++){
			d[0][k].x = d[1][k].x;
			d[0][k].y = d[1][k].y;
			d[0][k].dir = d[1][k].dir;
		}
		
		cost ++;
		end[0] = end[1], end[1] = 0;
		st = 1;
		if (end[0] == 0)
			s = 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;
}