Cod sursa(job #865850)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 ianuarie 2013 10:19:37
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair

using namespace std;
  
ifstream cin("car.in");
ofstream cout("car.out");
				
const int dx[] = {-1,-1,0,1,1,1,0,-1}, dy[] = {0,1,1,1,0,-1,-1,-1};
const int NMAX = 512, inf = int(1e9);
int N, M;
bool isFree[NMAX][NMAX];
int cost[NMAX][NMAX][8];
pii S, D;

void readData() {
	cin>>N>>M;
	cin>>S.x>>S.y>>D.x>>D.y;
	for(int i = 1;i <= N;i++) {
		for(int j = 1;j <= M;j++) {
			cin>>isFree[i][j];
		}
	}
}

int bf() {
	for(int i = 1;i <= N;i++) { 
		for(int j = 1;j <= M;j++) {
			for(int k = 0;k < 8;k++) {
				cost[i][j][k] = inf;	
			}
			isFree[i][j] = !isFree[i][j];
		}
	}
	queue< pair<pii,int> > q;
	if(isFree[S.x][S.y]) {
		for(int k = 0;k < 8;k++) {
			cost[S.x][S.y][k] = 0;
			q.push(mp(S,k));
		}
	}
	pii v, w;
	int dir;
	while(!q.empty()) {
		v = q.front().x;
		dir = q.front().y;
		q.pop();
		for(int k = 0;k < 8;k++) {
			int d = dir + k, c;
			d -= d < 8 ? 0 : 8;
			c = k < 4 ? k : k - 4;
			if(k > 0 && !c) c = 4;
			w = mp(v.x + dx[d],v.y + dy[d]);
			if(isFree[w.x][w.y]) {
				if(cost[w.x][w.y][d] > cost[v.x][v.y][dir] + c) { 
					cost[w.x][w.y][d] = cost[v.x][v.y][dir] + c;
					q.push(mp(w,d));
				}
			}
		}
	}
	int ans = inf;
	for(int k = 0;k < 8;k++) {
		ans = min(ans,cost[D.x][D.y][k]);
	}
	return ans == inf ? -1 : ans;
}

int main()
{
	readData();
	cout<<bf();
    return 0;
}