Cod sursa(job #159338)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 08:17:59
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>

using namespace std;

const int dir[8][2] = {
	{1, 0},
	{1, 1},
	{0, 1},
	{-1, 1},
	{-1, 0},
	{-1, -1},
	{0, -1},
	{1, -1}
};

int N, M,
	Si, Sj, Fi, Fj,
	a[502][502];
int cod[502*502*8],
	sf,
	sol = 0;
int m[8][502][502];

void adauga(int sx, int sy, int d, int cost) {
	int i, j;
	for (i = sx, j = sy; !a[i][j]; i += dir[d][0], j += dir[d][1]) // merge intr-o directie pana cand gaseste un 0
		if (!m[d][i][j]) {
			m[d][i][j] = cost;
			cod[++sf] = (((i<<9)+j)<<3)+d;
			if ((i == Fi) && (j == Fj))
				sol = cost;
		}
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("car.in", "r");	
	fscanf(fi, "%d %d", &N, &M);
	fscanf(fi, "%d %d %d %d", &Si, &Sj, &Fi, &Fj);
	for (int i(0); i <= N + 1; ++i)
		for (int j(0); j <= M + 1; ++j)
			a[i][j] = 1;
	for (int i(1); i <= N; ++i)
		for (int j(1); j <= M; ++j)
			fscanf(fi, "%d", &a[i][j]);
	fclose(fi);

	sf = -1;
	for (int i(0); i < 8; ++i)
		adauga(Si, Sj, i, 1);

	for (int Q(0); (Q <= sf) && (!sol); ++Q) {
		int i = cod[Q]>>12;
		int j = (cod[Q]&4088)>>3;
		int d = cod[Q]&7;
		adauga(i, j, (d + 1) % 8, m[d][i][j] + 1); // 45 la dreapta
		adauga(i, j, (d + 8 - 1) % 8, m[d][i][j] + 1); // 45 la stanga
	}

	ofstream fout("car.out");
	fout << sol-1 << endl;
	fout.close();

	return 0;
}