Pagini recente » Cod sursa (job #1345837) | Cod sursa (job #164670) | Cod sursa (job #1388752) | Cod sursa (job #2225870) | Cod sursa (job #1726100)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int nmax = 505;
const int INF = 2000000000;
int n,m,a[nmax][nmax],Si,Sj,Fi,Fj,ans;
int dp[nmax][nmax][10];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
struct el
{
int x,y,dir,cost;
};
queue < el > Q0,Q1;
inline bool OK(int i, int j)
{
if(i < 1 || j < 1 || i > n || j > m || a[i][j]) return false;
return true;
}
inline void Read()
{
int i,j,k;
el E;
fin >> n >> m;
fin >> Si >> Sj >> Fi >> Fj;
for(i = 1; i <= n; i++)
for(j = 1 ; j <= m; j++)
{
fin >> a[i][j];
for(k = 0; k < 8 ;k++) dp[i][j][k] = INF;
}
for(k = 0; k < 8; k++)
{
E.x = Si, E.y = Sj;
E.cost = 0;
E.dir = k;
Q0.push(E);
}
}
inline void Dijkstra()
{
int i,j,k;
el E,W;
while(!Q0.empty())
{
while(!Q0.empty())
{
E = Q0.front();
Q0.pop();
W.cost = E.cost, W.dir = E.dir;
W.x = E.x + dx[E.dir];
W.y = E.y + dy[E.dir];
if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
dp[W.x][W.y][W.dir] = W.cost;
Q0.push(W);
}
W.cost++;
W.dir = (E.dir + 1)%8;
W.x = E.x;
W.y = E.y;
if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
Q1.push(W);
dp[W.x][W.y][W.dir] = W.cost;
}
W.dir = (E.dir -1);
if(W.dir < 0) W.dir = 7;
if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
{
Q1.push(W);
dp[W.x][W.y][W.dir] = W.cost;
}
}
while(!Q1.empty())
{
E = Q1.front();
Q1.pop();
Q0.push(E);
}
}
}
inline void Afisare()
{
ans = dp[Fi][Fj][0];
for(int i = 1; i < 8; i++) ans = min(ans,dp[Fi][Fj][i]);
fout << (ans == INF? -1 : ans) << "\n";
fout.close();
}
int main()
{
Read();
Dijkstra();
Afisare();
return 0;
}