Pagini recente » Cod sursa (job #59268) | Cod sursa (job #2536786) | Cod sursa (job #322106) | Cod sursa (job #3128333) | Cod sursa (job #2905613)
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
int d[505][505][10],n,m,ls,cs,lf,cf;
int a[505][505];
queue<pair<pair<int,int>,int>>q;
int dl[] = {-1,-1,0,1,1,1,0,-1};
int dc[] = {0,1,1,1,0,-1,-1,-1};
bool is[505][505][10];
void lee()
{
for (int i = 0; i < 8; i++)
q.push({{ls,cs},i}),d[ls][cs][i] = 0;
while (!q.empty())
{
pair<pair<int,int>,int>e = q.front();
is[e.first.first][e.first.second][e.second] = false;
q.pop();
for (int i = 0; i <= 7; i++)
{
int lin = e.first.first + dl[i],col = e.first.second + dc[i];
int dif = max(e.second,i) - min(e.second,i);
if (dif >= 5)
dif = 8 - dif;
if (d[lin][col][i] > d[e.first.first][e.first.second][e.second] + dif and lin >= 1 and lin <= n and col >= 1 and col <= m and a[lin][col] == 1)
{
d[lin][col][i] = d[e.first.first][e.first.second][e.second] + dif;
if (is[lin][col][i] == false)
{
q.push({{lin,col},i});
is[lin][col][i] = true;
}
}
}
}
}
int main()
{
for (int i = 1; i <= 500; i++)
for (int j = 1; j <= 500; j++)
for (int q = 1; q <= 10; q++)
d[i][j][q] = 1e9;
in >> n >> m >> ls >> cs >> lf >> cf;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
in >> a[i][j],a[i][j] = 1 - a[i][j];
lee();
int minim = 1e9;
for (int i = 0; i < 8; i++)
minim = min(minim,d[lf][cf][i]);
if (minim == 1e9)
out << -1;
else
out << minim;
return 0;
}