Cod sursa(job #930499)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 27 martie 2013 18:02:24
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <queue>
#include <cstring>
#define oo (1<<6)
#define nmax 510
#define Distance(Nod) (Distance[Nod.X][Nod.Y][Nod.Direction])
using namespace std;

struct Punct{int X,Y,Direction;}Start,End;
queue <Punct> Queue[2];
int N,M,Answer,A[nmax][nmax],Distance[nmax][nmax][8];
int Dx[]={-1,-1,-1,0,1,1,1,0},Dy[]={-1,0,1,1,1,0,-1,-1};

void bordare() {
	
	int i;
	
	memset(Distance,oo,sizeof(Distance));
	
	for(i=0;i<=N+1;i++)
		A[i][0]=A[i][M+1]=1;
	
	for(i=0;i<=M+1;i++)
		A[0][i]=A[N+1][i]=1;
	
}
void solve() {

    int i,step,List[]={0,1,7};
	Punct Nod,Vecin;

    Answer=-1;
	bordare();

    for(i=0;i<8;i++) {
        Start.Direction=i;
        Distance(Start)=0;
        Queue[0].push(Start);
        }
	
	for(step=0;!Queue[step].empty();step^=1) {
		
		while(!Queue[step].empty()) {
			
			Nod=Queue[step].front();
			Queue[step].pop();
			
			if(Nod.X==End.X && Nod.Y==End.Y) {
				Answer=Distance(Nod);
				return;
				}
			
			for(i=0;i<3;i++) {
				
				Vecin.X=Nod.X+(!i)*Dx[(Nod.Direction+List[i])&7];
				Vecin.Y=Nod.Y+(!i)*Dy[(Nod.Direction+List[i])&7];
				Vecin.Direction=(Nod.Direction+List[i])&7;
				
				if( !A[Vecin.X][Vecin.Y] && Distance(Vecin) > Distance(Nod) + (List[i]!=0) ) {
					Distance(Vecin) = Distance(Nod) + (List[i]!=0);
					Queue[step^(List[i]!=0)].push(Vecin);
					}
				
				}
			
			}
		
		}

}
void read() {

    int i,j;
    char S[nmax>>1];

    ifstream in("car.in");
    in>>N>>M>>Start.X>>Start.Y>>End.X>>End.Y;
    in.getline(S+1,nmax>>1);

    for(i=1;i<=N;i++) {
		
        in.getline(S+1,nmax>>1);
		
        for(j=1;j<=N;j++)
            A[i][j]=S[2*(j-1)+1]-48;
		
        }

    in.close();

}
void write() {

    ofstream out("car.out");
    out<<Answer<<'\n';
    out.close();

}
int main() {

    read();
    solve();
    write();

    return 0;

}