Pagini recente » Cod sursa (job #1681906) | Cod sursa (job #3285637) | Cod sursa (job #2279797) | Cod sursa (job #2246843) | Cod sursa (job #1347871)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const short inceput = 2;
template <class T>
void bfs(vector<vector<T>>& oras, int x1, int y1)
{
int n = oras.size();
int m = oras[0].size();
queue<pair<int, int>> qu;
qu.push(make_pair(x1, y1));
int deltay[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int deltax[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int cost[8][8] = { { 0, 1, 2, 3, 4, 3, 2, 1 } };
for (int i = 1, lim = sizeof(deltax) / sizeof(int); i < lim; i++)
{
int temp = cost[i - 1][lim - 1];
for (int j = 0; j < lim - 1; j++)
{
cost[i][j + 1] = cost[i - 1][j];
}
cost[i][0] = temp;
}
int directii[] = { 7, 0, 1, 2, 3, 4, 5, 6 };
vector<vector<char>> directie(n, vector<char>(m));
directie[x1][y1] = -1;
while (!qu.empty())
{
int x = qu.front().first;
int y = qu.front().second;
qu.pop();
for (int i = 0; i < sizeof(deltax) / sizeof(int); i++)
{
int newx = x + deltax[i];
int newy = y + deltay[i];
try
{
if (newx >= 0 && newx < m && newy >= 0 && newy < n)
{
if (oras[newx][newy] != 1)
{
if (oras[newx][newy] == 0)
{
directie[newx][newy] = directii[i];
if (directie[x][y] == -1)
{
oras[newx][newy] = oras[x][y];
}
else
{
oras[newx][newy] = oras[x][y] + cost[directie[x][y]][directie[newx][newy]];//
}
qu.push(make_pair(newx, newy));
}
else
{
if (oras[newx][newy] > oras[x][y] + cost[directie[x][y]][directii[i]])//
{
directie[newx][newy] = directii[i];
oras[newx][newy] = oras[x][y] + cost[directie[x][y]][directie[newx][newy]];//
qu.push(make_pair(newx, newy));
}
}
}
}
}
catch (exception e)
{
cout << e.what();
}
}
}/*
for (auto& linie : oras)
{
for (auto& casuta : linie)
{
cout << casuta << ' ';
}
cout << endl;
}*/
}
int main()
{
ifstream in("car.in");
int n, m;
in >> n >> m;
int x1, y1, x2, y2;
in >> x1 >> y1 >> x2 >> y2;
vector<vector<short>> oras(n, vector<short>(m));
for (auto& linie : oras)
{
for (auto& casuta : linie)
{
in >> casuta;
}
}
oras[x1 - 1][y1 - 1] = inceput;
in.close();
bfs(oras, x1 - 1, y1 - 1);
ofstream out("car.out");
if (oras[x2 - 1][y2 - 1] == 0)
{
out << -1;
}
else
{
out << oras[x2 - 1][y2 - 1] - inceput;
}
out.close();
return 0;
}