#include #define ld long double using namespace std; const ld INF = 1e18; const ld TWOSQRTTWO = (ld)2 * sqrtl(2); const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int n, m, sx, sy, ex, ey; inline bool check(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m >> sy >> sx >> ey >> ex; n /= 2; m /= 2; int a[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } ld dp[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = INF; } } set < pair < ld, pair < int, int > > > q; dp[sx / 2][sy / 2] = 0; q.insert(make_pair(0, make_pair(sx / 2, sy / 2))); while (!q.empty()) { int x = q.begin()->second.first, y = q.begin()->second.second; q.erase(q.begin()); // horizontal and vertical for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (check(xx, yy) && dp[xx][yy] > dp[x][y] + TWOSQRTTWO + abs(a[x][y] - a[xx][yy])) { q.erase(make_pair(dp[xx][yy], make_pair(xx, yy))); dp[xx][yy] = dp[x][y] + TWOSQRTTWO + abs(a[x][y] - a[xx][yy]); q.insert(make_pair(dp[xx][yy], make_pair(xx, yy))); } } // left up if (check(x - 1, y - 1)) { int xx = x - 1, yy = y - 1; ld val = TWOSQRTTWO + abs(a[x][y] - max(a[x][y - 1], a[x - 1][y])) + abs(a[xx][yy] - max(a[x][y - 1], a[x - 1][y])); if (dp[xx][yy] > dp[x][y] + val) { q.erase(make_pair(dp[xx][yy], make_pair(xx, yy))); dp[xx][yy] = dp[x][y] + val; q.insert(make_pair(dp[xx][yy], make_pair(xx, yy))); } } // right up if (check(x - 1, y + 1)) { int xx = x - 1, yy = y + 1; ld val = TWOSQRTTWO + abs(a[x][y] - max(a[x][y + 1], a[x - 1][y])) + abs(a[xx][yy] - max(a[x][y + 1], a[x - 1][y])); if (dp[xx][yy] > dp[x][y] + val) { q.erase(make_pair(dp[xx][yy], make_pair(xx, yy))); dp[xx][yy] = dp[x][y] + val; q.insert(make_pair(dp[xx][yy], make_pair(xx, yy))); } } // left down if (check(x + 1, y - 1)) { int xx = x + 1, yy = y - 1; ld val = TWOSQRTTWO + abs(a[x][y] - max(a[x][y - 1], a[x + 1][y])) + abs(a[xx][yy] - max(a[x][y - 1], a[x + 1][y])); if (dp[xx][yy] > dp[x][y] + val) { q.erase(make_pair(dp[xx][yy], make_pair(xx, yy))); dp[xx][yy] = dp[x][y] + val; q.insert(make_pair(dp[xx][yy], make_pair(xx, yy))); } } // right down if (check(x + 1, y + 1)) { int xx = x + 1, yy = y + 1; ld val = TWOSQRTTWO + abs(a[x][y] - max(a[x][y + 1], a[x + 1][y])) + abs(a[xx][yy] - max(a[x][y + 1], a[x + 1][y])); if (dp[xx][yy] > dp[x][y] + val) { q.erase(make_pair(dp[xx][yy], make_pair(xx, yy))); dp[xx][yy] = dp[x][y] + val; q.insert(make_pair(dp[xx][yy], make_pair(xx, yy))); } } } cout << fixed << setprecision(4) << dp[ex / 2][ey / 2]; }