Cod sursa(job #1735057)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 iulie 2016 19:24:48
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define NMAX 505
#define MOD 666013

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

int v[NMAX][NMAX], viz[NMAX][NMAX][8];
int dlin[8]={0,-1,-1,-1,0,1,1,1};
int dcol[8]={1,1,0,-1,-1,-1,0,1};
queue<int> Q[2];
inline int code(int x, int y, int dir) {return (x<<12)+(y<<3)+dir;}

int main() {
	int i,j,n,m,x0,x1,y1,y0,distact,ind,fr,x,y,dir;

	fin>>n>>m>>x0>>y0>>x1>>y1;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j) fin>>v[i][j];

	for(i=0;i<=n+1;++i) v[i][0]=v[i][m+1]=1;
	for(i=0;i<=m+1;++i) v[0][i]=v[n+1][i]=1;

	for(i=0;i<8;++i) Q[0].push(code(x0,y0,i));
	distact=0;
	while(!Q[0].empty() || !Q[1].empty()) {
		ind=distact&1;

		while(!Q[ind].empty()) {
			fr=Q[ind].front();
			Q[ind].pop();
			x=fr>>12;
			y=(fr>>3)&511;
			dir=fr&7;

			if(x==x1 && y==y1) {
				fout<<distact;
				return 0;
			}

			if(!v[x][y] && !viz[x][y][dir]) {
				viz[x][y][dir]=1;

				if(!v[x+dlin[dir]][y+dcol[dir]] && !viz[x+dlin[dir]][y+dcol[dir]][dir])
					Q[ind].push(code(x+dlin[dir],y+dcol[dir],dir));

				for(j=(dir+7)&7;j!=((dir+3)&7); j=(j+2)&7)
					if(!viz[x][y][j]) Q[(ind+1)&1].push(code(x,y,j));
			}
		}
		++distact;
	}

	fout<<-1;

	return 0;
}