Cod sursa(job #338939)
Utilizator | Data | 7 august 2009 16:07:47 | |
---|---|---|---|
Problema | Car | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.74 kb |
#include <stdio.h>
#include <queue>
using namespace std;
#define Nmax 505
#define x first
#define y second
int A[Nmax][Nmax];
int v[Nmax][Nmax],d[Nmax][Nmax];
queue< pair<int,int> > Q;
int n,m,xi,yi,xf,yf;
const int dx[8]={-1,-1,0,1,1,1,0,-1};
const int dy[8]={0,1,1,1,0,-1,-1,-1};
const int cost[8]={0,1,2,3,4,3,2,1};
void read(){
int i,j;
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
scanf("%d%d\n",&n,&m);
scanf("%d%d%d%d",&xi,&yi,&xf,&yf);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&A[i][j]);
}
int in_oras(int x,int y){
if(x<=0 || x>n || y<=0 || y>m) return 0;
return 1;
}
void work(){
int k,xx,yy;
pair<int,int> p;
v[xi][yi]=1;
p=make_pair(xi,yi);
for(k=0;k<8;k++){
xx=p.x+dx[k];
yy=p.y+dy[k];
if(in_oras(xx,yy) && !A[xx][yy]){
d[xx][yy]=k,v[xx][yy]=1;
Q.push(make_pair(xx,yy));
}
}
while(!Q.empty()){
p=Q.front();
for(k=0;k<8;k++){
xx=p.x+dx[k];
yy=p.y+dy[k];
if(in_oras(xx,yy) && !A[xx][yy] ){
if(!v[xx][yy]){
v[xx][yy]=v[p.x][p.y]+cost[abs(d[p.x][p.y]-k)];
d[xx][yy]=k;
Q.push(make_pair(xx,yy));
}
else
if(v[xx][yy]>v[p.x][p.y]+cost[abs(d[p.x][p.y]-k)]){
v[xx][yy]=v[p.x][p.y]+cost[abs(d[p.x][p.y]-k)];
d[xx][yy]=k;
Q.push(make_pair(xx,yy));
}
// printf("in %d %d este v %d si d %d\n",xx,yy,
// v[xx][yy],d[xx][yy]);
}
}
Q.pop();
}
}
void write(){
printf("%d\n",v[xf][yf]-1);
fclose(stdin); fclose(stdout);
}
int main(){
read();
work();
write();
return 0;
}