Pagini recente » Cod sursa (job #2765775) | Cod sursa (job #288472) | Cod sursa (job #2650132) | Cod sursa (job #2894291) | Cod sursa (job #1393665)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
fstream fin("car.in", ios::in);
fstream fout("car.out", ios::out);
#define MAXDIM 510
int m, n, map[MAXDIM][MAXDIM], minn = 250000;
queue <pair<int, pair<int, int>>> q;
pair<int, int> final;
bool first = true, used[MAXDIM][MAXDIM];
void read()
{
int x, y, w, z;
fin >> n >> m;
fin >> x >> y >> w >> z;
q.push(make_pair(x, make_pair(y, 0)));
final = make_pair(w, z);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> x,
map[i][j] = x;
fin.close();
}
void neighbour(int old_cost, int next_i, int next_j, int way )
{
if (next_i > n || next_i < 1 || next_j > m || next_j < 1 || map[next_i][next_j] != 0) return;
int dif = abs(q.front().second.second - way), cost, next_way = way < 5 ? way + 4 : way - 4;
if (first) cost = 0;
else cost = dif == 4 ? 0 : dif == 3 || dif == 5 ? 1 : dif == 6 || dif == 2 ? 2 : dif == 1 || dif == 7 ? 3 : 4;
if ((map[next_i][next_j] > cost + old_cost || used[next_i][next_j] == false) && dif != 0)
q.push(make_pair(next_i, make_pair(next_j, next_way))),
map[next_i][next_j] = old_cost + cost,
used[next_i][next_j] = true;
}
void LEE()
{
int i, j, way, next_i, next_j;
used[q.front().first][q.front().second.first] = true;
while (!q.empty()){
i = q.front().first, j = q.front().second.first, way = q.front().second.second;
for (int k = 1; k <= 8; k++){
k < 4 ? next_i = -1 : k > 4 && k < 8 ? next_i = 1 : next_i = 0;
k > 6 || k == 1 ? next_j = -1 : k > 2 && k < 6 ? next_j = 1 : next_j = 0;
neighbour(map[i][j], i + next_i, j + next_j, k);
}
if (i == final.first && j == final.second && map[i][j] < minn)
minn = map[i][j];
q.pop();
first = false;
}
}
int main()
{
read();
LEE();
if (minn == 250000) fout << -1;
else fout << minn;
fout.close();
return 0;
}