Pagini recente » Cod sursa (job #2098735) | Cod sursa (job #1194912) | Cod sursa (job #2682319) | Cod sursa (job #1146631) | Cod sursa (job #1527708)
#include <cstdio>
#include <queue>
using namespace std;
FILE *f,*g;
int n,m;
int d[510][510][8];
int a[510][510];
bool in[510][510][8];
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;
}
int abs(int x)
{
if (x<0) return -x;
return x;
}
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();
in[now.p.x][now.p.y][now.dir] = false;
bool ok2 = false;
int dir1 = (now.dir + 1) %8;
if (d[now.p.x][now.p.y][dir1] == 0 || d[now.p.x][now.p.y][dir1] > d[now.p.x][now.p.y][now.dir] + 1)
{
d[now.p.x][now.p.y][dir1] = d[now.p.x][now.p.y][now.dir] + 1;
if (!in[now.p.x][now.p.y][dir1])
{
q.push(stare(now.p, dir1));
in[now.p.x][now.p.y][dir1] = true;
}
}
dir1 = (now.dir + 7) %8;
if (d[now.p.x][now.p.y][dir1] == 0 || d[now.p.x][now.p.y][dir1] > d[now.p.x][now.p.y][now.dir] + 1)
{
d[now.p.x][now.p.y][dir1] = d[now.p.x][now.p.y][now.dir] + 1;
if (!in[now.p.x][now.p.y][dir1])
{
q.push(stare(now.p, dir1));
in[now.p.x][now.p.y][dir1] = true;
}
}
for (int k = -1;k <= 1;k++)
{
int i = (now.dir + k + 8) % 8;
if (ok(now.p + i))
{
ok2 = true;
stare then = stare( now.p + i, i);
int add_cost = abs(k);
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;
if (!in[then.p.x][then.p.y][i])
{
q.push(then);
in[then.p.x][then.p.y][i] = true;
}
}
}
}
}
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];
}
fprintf(g,"%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;
}