Pagini recente » Cod sursa (job #2543933) | Cod sursa (job #2879313) | Cod sursa (job #2525865) | Cod sursa (job #2323784) | Cod sursa (job #1527673)
#include <cstdio>
#include <queue>
using namespace std;
FILE *f,*g;
int n,m;
int d[510][510][8];
int a[510][510];
int dx[8] = {-1,-1,-1,0,+1,+1,+1,0};
int dy[8] = {-1,0,+1,+1,+1,0,-1,-1};
struct point
{
int x,y;
point(){}
point(int X,int Y):x(X),y(Y){}
point operator+(int dir)
{
return point(dx[dir]+x, dy[dir]+y);
}
};
struct stare
{
point p;
int dir;
stare(){}
stare(point P, int d):p(P),dir(d){}
int operator-(stare other)
{
int mn = min(dir, other.dir);
int mx = max(dir, other.dir);
return min(mx-mn , 8-mx+mn);
}
};
point st,dr;
bool ok(point p)
{
if (p.x < 1 || p.x > n || p.y < 1 || p.y > m || a[p.x][p.y] == 1) return false;
return true;
}
void solve()
{
queue<stare> q;
for (int i = 0;i < 8; i++)
{
d[st.x][st.y][i] = 1;
q.push(stare(st,i));
}
while (q.size())
{
stare now = q.front();
q.pop();
for (int i = 0;i < 8;i++)
{
if (ok(now.p + i))
{
stare then = stare( now.p + i, i);
int add_cost = now - then;
if (d[then.p.x][then.p.y][i] == 0 || d[then.p.x][then.p.y][i] > d[now.p.x][now.p.y][now.dir] + add_cost)
{
d[then.p.x][then.p.y][i] = d[now.p.x][now.p.y][now.dir] + add_cost;
q.push(then);
}
}
}
}
int ans = 0;
for (int i =0;i < 8;i++)
if (d[dr.x][dr.y][i] > 0)
{
if (ans == 0 || ans > d[dr.x][dr.y][i])
ans = d[dr.x][dr.y][i];
}
printf("%d",ans-1);
}
int main()
{
f = fopen("car.in","r");
g = fopen("car.out","w");
fscanf(f,"%d%d",&n,&m);
fscanf(f,"%d%d%d%d",&st.x, &st.y, &dr.x, &dr.y);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
fscanf(f,"%d",&a[i][j]);
solve();
return 0;
}