Pagini recente » Cod sursa (job #691179) | Cod sursa (job #2635745) | Cod sursa (job #1029497) | Cod sursa (job #3131197) | Cod sursa (job #3254670)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin ("car.in");
ofstream fout("car.out");
const vector<int> dx({-1, -1, -1, 0, 0, 1, 1, 1});
const vector<int> dy({-1, 0, 1, -1, 1, -1, 0, 1});
int n, m;
const int Max = 501;
vector<vector<int>> a(Max, vector<int>(Max));
bool verify(int x, int y)
{
return x >= 1 && y >= 1 && x <= n && y <= m;
}
int turn_cost(int x0, int y0, int x1, int y1, int x2, int y2)
{
if(x0 - x2 == y0 - y2)
return 0;
if(x0 == x2 && y0 == y2 - 2)
{
if(x1 == x2)
return 0;
return 2;
}
if(y0 == y2 && x0 == x2 - 2)
{
if(y1 == y2)
return 0;
return 2;
}
return 1;
}
void lee(int x, int y)
{
deque<pair<int,int>> q;
int old_x = x, old_y = y;
a[x][y] = 1;
for(int d = 0; d < 8; ++d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
if(verify(new_x, new_y) && !a[new_x][new_y])
{
a[new_x][new_y] = 1;
q.push_front({new_x, new_y});
}
}
while(!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop_front();
for(int d = 0; d < 8; ++d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
int cost = turn_cost(old_x, old_y, x, y, new_x, new_y);
if(verify(new_x, new_y) && (a[x][y] + cost < a[new_x][new_y] || !a[new_x][new_y]))
{
a[new_x][new_y] = a[x][y] + cost;
old_x = x;
old_y = y;
if(!cost)
q.push_front({new_x, new_y});
else
q.push_back({new_x, new_y});
}
}
}
}
int main()
{
int s1, s2, f1, f2;
fin >> n >> m >> s1 >> s2 >> f1 >> f2;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
fin >> a[i][j];
lee(s1, s2);
fout << a[f1][f2] - 1;
fin.close();
fout.close();
return 0;
}