Pagini recente » Cod sursa (job #1329950) | Cod sursa (job #501867) | Cod sursa (job #19220) | Cod sursa (job #2285120) | Cod sursa (job #2174681)
#include <iostream>
#include <fstream>
#define oo 1<<30
#define Nmax 505
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
struct nod{
int x,y;
};
nod heap[Nmax*Nmax];
nod S,F;
int Ux[] = {0,1,1,1,0,-1,-1,-1};
int Uy[] = {1,1,0,-1,-1,-1,0,1};
int A[Nmax][Nmax],C[Nmax][Nmax],D[Nmax][Nmax],P[Nmax][Nmax];
int Nheap,N,M;
void upheap(int node){
int tata = node/2;
if(node==1)
return;
if(C[heap[node].x][heap[node].y]<=C[heap[tata].x][heap[tata].y]){
swap(P[heap[node].x][heap[node].y],P[heap[tata].x][heap[tata].y]);
swap(heap[node],heap[tata]);
upheap(tata);
}
}
void downheap(int node){
int son1 = node*2;
int son2 = son1+1;
if(son1 > Nheap)
return;
if(son1 == Nheap){
if(C[heap[son1].x][heap[son1].y]<=C[heap[node].x][heap[node].y]){
swap(P[heap[node].x][heap[node].y],P[heap[son1].x][heap[son1].y]);
swap(heap[son1],heap[node]);
downheap(son1);
}
return;
}
if(son1<Nheap){
if(C[heap[son1].x][heap[son1].y]<=C[heap[son2].x][heap[son2].y]){
if(C[heap[son1].x][heap[son1].y]<=C[heap[node].x][heap[node].y]){
swap(P[heap[node].x][heap[node].y],P[heap[son1].x][heap[son1].y]);
swap(heap[son1],heap[node]);
downheap(son1);
}
return;
}else{
if(C[heap[son2].x][heap[son2].y]<=C[heap[node].x][heap[node].y]){
swap(P[heap[node].x][heap[node].y],P[heap[son2].x][heap[son2].y]);
swap(heap[son2],heap[node]);
downheap(son2);
}
return;
}
}
}
int abs(int x){
if(x<0)
return -x;
return x;
}
int main()
{
fin>>N>>M;
fin>>S.x>>S.y>>F.x>>F.y;
for(int i=1 ;i<=N;i++){
for(int j=1;j<=M;j++){
fin>>A[i][j];
C[i][j] =oo;
}
}
for(int i=0;i<=N+1;i++){
A[i][0] = A[i][M+1] = 1;
}
for(int i=0;i<=M+1;i++){
A[0][i] = A[N+1][i] = 1;
}
C[S.x][S.y] = 0;
for(int i=0;i<8;i++){
nod nn;
nn.x = S.x+Ux[i];
nn.y = S.y+Uy[i];
int c = 0;
if(A[nn.x][nn.y]==1)
continue;
if(C[S.x][S.y]+c<C[nn.x][nn.y]){
C[nn.x][nn.y] = C[S.x][S.y]+c;
D[nn.x][nn.y] = i;
Nheap++;
P[nn.x][nn.y] = Nheap;
heap[Nheap] = nn;
upheap(Nheap);
}
}
while(Nheap){
nod cur = heap[1];
swap(heap[1],heap[Nheap]);
Nheap--;
downheap(1);
A[cur.x][cur.y] = 1;
nod nn;
for(int i=0;i<8;i++){
nn.x = cur.x+Ux[i];
nn.y = cur.y+Uy[i];
if(A[nn.x][nn.y]==1)
continue;
int c = min(abs(i-D[cur.x][cur.y]),8-abs(i-D[cur.x][cur.y]));
if(C[cur.x][cur.y]+c<C[nn.x][nn.y]){
C[nn.x][nn.y] = C[cur.x][cur.y]+c;
D[nn.x][nn.y] = i;
if(P[nn.x][nn.y] ==0){
Nheap++;
P[nn.x][nn.y] = Nheap;
heap[Nheap] = nn;
upheap(Nheap);
}
else{
upheap(P[nn.x][nn.y]);
}
}
}
}
fout<<C[F.x][F.y];
return 0;
}