Pagini recente » Cod sursa (job #1795950) | Cod sursa (job #2092579) | Cod sursa (job #1599827) | Cod sursa (job #3246222) | Cod sursa (job #1105637)
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define NM 510
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
const int INF=0x3f3f3f3f;
const int dx[8]={1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
int N, M, C, P;
int A[NM][NM], DP[8][NM][NM];
int sl, sc, fl, fc;
queue< pair<pair<int, int>, int> > Q[2];
int main ()
{
f >> N >> M;
f >> sl >> sc >> fl >> fc;
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
{
f >> A[i][j];
A[i][j]=1-A[i][j];
}
memset(DP, INF, sizeof(DP));
for (int d=0; d<8; d++)
{
Q[0].push(make_pair(make_pair(sl, sc), d));
DP[d][sl][sc]=0;
}
C=0;
P=1;
while (!Q[C].empty() || !Q[P].empty())
{
if (Q[C].empty())
swap(P, C);
int i=Q[C].front().first.first;
int j=Q[C].front().first.second;
int d=Q[C].front().second;
Q[C].pop();
if (A[i+dx[d]][j+dy[d]]==1 && DP[d][i+dx[d]][j+dy[d]]>DP[d][i][j])
{
DP[d][i+dx[d]][j+dy[d]]=DP[d][i][j];
Q[C].push(make_pair(make_pair(i+dx[d], j+dy[d]), d));
}
for (int nd=-1; nd<=1; nd+=2)
if (DP[(d+nd+8)%8][i][j]>DP[d][i][j]+1)
{
DP[(d+nd+8)%8][i][j]=DP[d][i][j]+1;
Q[P].push(make_pair(make_pair(i, j), (d+nd+8)%8));
}
}
int ANS=INF;
for (int d=0; d<8; d++)
ANS=min(ANS, DP[d][fl][fc]);
g << (ANS==INF?-1:ANS) << '\n';
f.close();
g.close();
return 0;
}