#include #define FOR(i, n) for(int i = 0; i < (n); ++i) #define REP(i, a, b) for(int i = (a); i < (b); ++i) #define TRAV(i, a) for(auto & i : (a)) #define SZ(x) ((int)(x).size()) #define X first #define Y second #define PR std::pair #define MP std::make_pair typedef long long ll; typedef std::pair PII; typedef std::vector VI; struct pt { int x, y; pt() {} pt(int _x, int _y) : x(_x), y(_y) {} pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); } ll cross(const pt& p) const { return 1ll * x * p.y - 1ll * y * p.x; } ll cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); } }; bool operator<(pt a, pt b){ if(a.x == b.x) return a.y < b.y; return a.x < b.x; } int sgn(const long long& x) { return x >= 0 ? x ? 1 : 0 : -1; } bool inter1(int a, int b, int c, int d) { if (a > b) std::swap(a, b); if (c > d) std::swap(c, d); return std::max(a, c) <= std::min(b, d); } bool check_inter(const pt& a, const pt& b, const pt& c, const pt& d) { if (c.cross(a, d) == 0 && c.cross(b, d) == 0) return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y); return sgn(a.cross(b, c)) != sgn(a.cross(b, d)) && sgn(c.cross(d, a)) != sgn(c.cross(d, b)); } ll dst(pt a, pt b){ return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int w, h; std::cin >> w >> h; assert(w % 2 == 0); assert(h % 2 == 0); pt start, end; std::cin >> start.x >> start.y >> end.x >> end.y; if(start.x == end.x && start.y == end.y){ std::cout << "0.00000000\n"; return 0; } assert(start.x % 2 == 1); assert(start.y % 2 == 1); assert(end.x % 2 == 1); assert(end.y % 2 == 1); std::vector tab(w/2, VI(h/2)); FOR(j, h/2){ FOR(i, w/2){ std::cin >> tab[i][j]; } } std::vector> przec; double ans = 0; ans += std::sqrt(dst(start, end)); std::vector path; for(int i = 0; i < w; i += 2){ for(int j = 0; j < h; j += 2){ std::vector corners{ pt(i, j), pt(i + 2, j), pt(i + 2, j + 2), pt(i, j + 2) }; int cnt = 0; FOR(k, 4){ if(check_inter(corners[k], corners[(k+1)%4], start, end)){ cnt = 1; } } if(cnt){ path.push_back(pt(i / 2, j / 2)); } } } std::vector spec(w/2, VI(h/2)); for(int i = 2; i < w; i += 2){ for(int j = 2; j < h; j += 2){ std::vector heh{ pt(i-1, j), pt(i+1, j), pt(i, j+1), pt(i, j-1) }; int cnt = 0; FOR(k, 4){ if(check_inter(heh[k], pt(i, j), start, end)){ cnt++; } } assert(cnt != 3); if(cnt == 4){ spec[i/2][j/2] = 1; spec[i/2-1][j/2] = 1; spec[i/2][j/2-1] = 1; spec[i/2-1][j/2-1] = 1; } } } std::sort(path.begin(), path.end(), [&](pt a, pt b){ a = pt(a.x*2+1, a.y*2+1); b = pt(b.x*2+1, b.y*2+1); return dst(a, start) < dst(b, start); }); FOR(i, SZ(path)-1){ auto pt = path[i]; auto nxt = path[i+1]; bool good = true; if(i+3 < SZ(path) && spec[pt.x][pt.y]){ FOR(j, 4) if(!spec[path[i+j].x][path[i+j].y]) good = false; }else{ good = false; } if(good){ int mn = std::min(tab[path[i+1].x][path[i+1].y], tab[path[i+2].x][path[i+2].y]); int src = tab[path[i].x][path[i].y]; int dest = tab[path[i+3].x][path[i+3].y]; if(mn > src){ ans += std::abs(src - mn); src = mn; } ans += std::abs(src - dest); i += 2; }else{ int src = tab[path[i].x][path[i].y]; int dest = tab[path[i+1].x][path[i+1].y]; ans += std::abs(src - dest); } } std::cout << std::setprecision(12) << std::fixed << ans << "\n"; return 0; }