Pagini recente » Cod sursa (job #1399838) | Cod sursa (job #879030) | Cod sursa (job #147393) | Cod sursa (job #557020) | Cod sursa (job #3148363)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <cmath>
std::ifstream fin("car.in");
std::ofstream fout("car.out");
int x, y;
int is, js, ie, je;
int arr[501][501];
int dist[501][501][8];
int cost[8][8];
const int dx[] = {-1,-1,0,1,1,1,0,-1};
const int dy[] = {0,1,1,1,0,-1,-1,-1};
inline bool in_mat(int i, int j) {
return !(i<1||i>x||j<1||j>y);
}
void bfs(int is, int js, int init_dir) {
std::queue<std::tuple<int,int,int>> q;
q.emplace(is,js,init_dir);
dist[is][js][init_dir] = 0;
int i, j, d;
while (!q.empty()) {
std::tie(i,j,d) = q.front();
q.pop();
for (int k = 0; k < 8; k++) {
const int inou = i+dx[k];
const int jnou = j+dy[k];
int c = cost[d][k];
if (in_mat(inou,jnou)&&!arr[inou][jnou]&&dist[inou][jnou][k]>dist[i][j][d]+c) {
dist[inou][jnou][k] = dist[i][j][d]+c;
q.emplace(inou,jnou,k);
}
}
}
}
int main() {
for (int i = 0; i < 8; i++) {
for (int j = 1; j <= 4; j++) {
cost[i][(i-j+8)&7] = cost[i][(i+j)&7] = j;
}
}
fin >> x >> y;
fin >> is >> js >> ie >> je;
for (int i = 1; i <= x; i++) {
for (int j = 1; j <= y; j++) {
fin >> arr[i][j];
}
}
memset(dist,0x3f,sizeof(dist));
for (int i = 0; i < 8; i++) {
bfs(is,js,i);
}
int ret = -1;
for (int i = 0; i < 8; i++) {
if (ret==-1||ret>dist[ie][je][i]) {
ret = dist[ie][je][i];
}
}
fout << ret << "\n";
}