Pagini recente » Cod sursa (job #2863736) | Cod sursa (job #979796) | Cod sursa (job #683518) | Cod sursa (job #683580) | Cod sursa (job #3254693)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
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 = 6;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
vector<vector<bool>> v(Max, vector<bool>(Max));
bool verify(int x, int y)
{
return x >= 1 && y >= 1 && x <= n && y <= m && !a[x][y];
}
int turn_cost(int x0, int y0, int x1, int y1, int x2, int y2)
{
if(x0 == x2)
{
if(x1 == x2)
return 0;
return 2;
}
if(y0 == y2)
{
if(y1 == y2)
return 0;
return 2;
}
if((x0 == x1 && x1 != x2) || (y0 == y1 && y1 != y2) || (x2 == x1 && x1 != x0) || (y2 == y1 && y1 != y0))
return 1;
if(x0 - x2 == y0 - y2 || x0 + x2 == y0 + y2)
return 0;
return -1;
}
void lee(int x, int y)
{
deque<pair<int,int>> q;
int old_x = x, old_y = y;
c[x][y] = 0;
v[x][y] = true;
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))
{
c[new_x][new_y] = 0;
q.push_back({new_x, new_y});
}
}
while(!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop_front();
if(v[x][y])
continue;
v[x][y] = true;
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(cost == -1)
continue;
if(verify(new_x, new_y) && c[x][y] + cost < c[new_x][new_y])
{
c[new_x][new_y] = c[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 << c[f1][f2];
fin.close();
fout.close();
return 0;
}