Pagini recente » Cod sursa (job #538237) | Cod sursa (job #692378) | Cod sursa (job #460555) | Cod sursa (job #1150563) | Cod sursa (job #217959)
Cod sursa(job #217959)
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int dx1[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int dy1[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
int a[503][503],xi,yi,xf,yf,n,m,dx[3][5000][9],dy[3][5000][9],dir[503],sl[503],nrnum,sf[4],cost,q,s1[503][503];
void bordare(){
for (int i=0; i<=m+1;i++){
a[0][i]=1;
a[n+1][i]=1;
}
for (int i=0; i<=n+1;i++){
a[i][0]=1;
a[i][m+1]=1;
}
}
void citire(){
fin>>n>>m>>xi>>yi>>xf>>yf;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
fin>>a[i][j];
}
int num(int x, int y){
s1[x][y]=50000;
int nr=0;
nr++;
for(int i=1;i<=8;i++){
int x1= x+dx1[i],y1=y+dy1[i];
if (s1[x1][y1]==0&&a[x1][y1]==0)
num(x1, y1);
}
return nr;
}
int ciclu(int x){
if(x<1)
return x+8;
if(x>8)
return x-8;
return x;
}
void drum(){
int viz[503][503],nn,nn1[503][503];
sf[0]=1;
for(int i=1;i<=8;i++){
dx[0][1][i]=xi;
dy[0][1][i]=yi;
}
nrnum=num(xi,yi);
for(int k=0;k<nrnum;){
q++;
while (q<=sf[0]){
for(int i=1;i<=8;i++){
int x=dx[0][q][i];
int y=dy[0][q][i];
for(int j=i-2;j<=i+2;j ++){
int j1=ciclu(j);
int x1=x+dx1[j1];
int y1=y+dy1[j1];
if(a[x1][y1]==0){
if(i<j)
nn=j-i;
else
nn=i-j;
if (nn1[x1][y1]==0){
sf[nn]++;
nn1[x1][y1]=1;
dx[nn][sf[nn]][j1]=x1;
dy[nn][sf[nn]][j1]=y1;
s1[x1][y1] =cost+nn;
}
else
if (nn+cost <s1[x1][y1]){
sf[nn]++;
dx[nn][sf[nn]][j1]=x1;
dy[nn][sf[nn]][j1]=y1;
s1[x1][y1] =cost+nn;
}
}
}
if(viz[x][y]==0){
viz[x][y]++;
k++;
}
}
}
int i=1;
for (k=1;k<=sf[i];k++)
for (int j=1;j<=8;j++){
dx[i-1][k][j]=dx[i][k][j];
dy[i-1][k][j]=dy[i][k][j];
}
i++;
for (k=1;k<=sf[i];k++)
for (int j=1;j<=8;j++){
dx[i-1][k][j]=dx[i][k][j];
dy[i-1][k][j]=dy[i][k][j];
}
q=1;
cost ++;
sf[0]=sf[1];
sf[1]=sf[2];
sf[2] = 0;
}
}
int main(){
citire();
bordare();
drum();
if(s1[xf][yf]==50000)
fout<<-1<<"\n";
else
fout<<s1[xf][yf]<<"\n";
fin.close();
fout.close();
return 0;
}