Pagini recente » Cod sursa (job #1581525) | Cod sursa (job #451221) | Cod sursa (job #787731) | Cod sursa (job #1313720) | Cod sursa (job #1723133)
#include<cstdio>
#include<bitset>
#include<vector>
#define MAXN 500
using namespace std;
bitset<MAXN+5> reach[8][MAXN+5];
int n,m,li,ci,lf,cf,answer=0,ok=0;
bool a[MAXN+5][MAXN+5];
int current;
struct State{
short int l;
short int c;
short int d;
};
int line[8]={-1,-1,-1,0,1,1,1,0};
int column[8]={-1,0,1,1,1,0,-1,-1};
vector<State> cost[4*MAXN*MAXN+5];
void Compute(int l,int c,int d){
State temp;
if(l<1||l>n||c<1||c>m||ok==1||a[l][c]==1)
return;
reach[d][l][c]=1;
if(l==lf&&c==cf){
answer=current;
ok=1;
return;
}
temp.l=l;
temp.c=c;
temp.d=d-1;
if(temp.d==-1)
temp.d=7;
if(reach[temp.d][l][c]==0)
cost[current+1].push_back(temp);
temp.d=d+1;
if(temp.d==8)
temp.d=0;
if(reach[temp.d][l][c]==0)
cost[current+1].push_back(temp);
if(reach[d][l+line[d]][c+column[d]]==0)
Compute(l+line[d],c+column[d],d);
}
int main(){
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
int i,j;
State start;
scanf("%d%d%d%d%d%d",&n,&m,&li,&ci,&lf,&cf);
start.l=li;
start.c=ci;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(i=0;i<8;i++){
reach[i][li][ci]=1;
start.d=i;
cost[1].push_back(start);
}
if(a[li][ci]==1||a[lf][cf]==1){
printf("-1");
return 0;
}
for(i=1;ok==0;i++){
if(i>4*n){
printf("-1");
return 0;
}
current=i;
for(j=0;j<cost[i].size();j++)
Compute(cost[i][j].l,cost[i][j].c,cost[i][j].d);
}
printf("%d",answer-1);
return 0;
}