Pagini recente » Cod sursa (job #1601733) | Cod sursa (job #1998500) | Cod sursa (job #1964147) | Cod sursa (job #381819) | Cod sursa (job #930508)
Cod sursa(job #930508)
#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;
}