Cod sursa(job #330836)

Utilizator cotofanaCotofana Cristian cotofana Data 11 iulie 2009 17:30:06
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <vector>
#define dim 501
#define dim2 1<<21+1

using namespace std;

int n, m, cost;
int xs, ys, xf, yf;
int a[dim][dim], dist[dim2];
const int dx[]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[]={0, 1, 1, 1, 0, -1, -1, -1};
vector<int> q[2];

int code(int i, int j, int dir) {
	return (i<<9)+j+(dir<<18);
}

void decode(int x, int &i, int &j, int &dir) {
	dir=x>>18;
	j=x&511;
	i=(x>>9)&511;
}

int expand(int x) {
	int i, j, dir, xr, xl, xfw;
	decode(x, i, j, dir);
	
	//+45 degrees
	xr=code(i, j, (dir+1)%8);
	if (dist[xr]>dist[x]+1) {
		q[(dist[x]+1)&1].push_back(xr);
		dist[xr]=dist[x]+1;
	}
	
	//-45 degrees
	xl=code(i, j, (dir-1+8)%8);
	if (dist[xl]>dist[x]+1) {
		q[(dist[x]+1)&1].push_back(xl);
		dist[xl]=dist[x]+1;
	}
	
	i+=dx[dir], j+=dy[dir];
	if (!i || !j || i>n || j>m || a[i][j]) return 0;
	if (i==xf && j==yf) return 1;
	
	//forward
	xfw=code(i, j, dir);
	if (dist[xfw]>dist[x]) {
		q[dist[x]&1].push_back(xfw);
		dist[xfw]=dist[x];
	}
	
	return 0;
}

int main() {
	int i, j, x;
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	
	scanf("%d %d\n", &n, &m);
	scanf("%d %d %d %d\n", &xs, &ys, &xf, &yf);
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j) scanf("%d ", &a[i][j]);
	
	for (i=0; i<dim2; ++i) dist[i]=1<<15;
	for (i=0; i<8; ++i) {
		x=code(xs, ys, i);
		q[0].push_back(x);
		dist[x]=0;
	}
	cost=0;
	
	while (q[0].size()+q[1].size()) {
		while (q[cost&1].size()) {
			x=q[cost&1][q[cost&1].size()-1];
			q[cost&1].pop_back();
			if (expand(x)==1) {
				printf("%d\n", cost);
				return 0;
			}
		}
		++cost;
	}
	
	printf("-1\n");
	
	return 0;
}