#include #include #include using namespace std; int my_min(int a, int b) { if (a == -1) return b; if (b == -1) return a; return min(a, b); } int adjust_height(int val, int left, int right) { int smaller = min(left, right); if (smaller > val) return (smaller - val); return 0; } int main() { int width, height, sx, sy, ex, ey; cin >> width >> height >> sx >> sy >> ex >> ey; vector> grid; grid.resize(height / 2); for (auto &g : grid) { g.resize(width / 2); } for (auto &row : grid) { for (int i = 0; i < row.size(); i++) { cin >> row[i]; // cout << row[i] << " "; } // cout << "\n"; } int dx = abs(ex - sx); int dy = abs(ey - sy); // Calculate horizontal distance double straight_dist = min(dx, dy) * sqrt(2) + (max(dx, dy) - min(dx, dy)); // cout << straight_dist << std::endl; vector> dp; dp.resize(height / 2); for (auto &g : dp) { g.resize(width / 2); } for (auto &row : dp) { for (int i = 0; i < row.size(); i++) { row[i] = -1; // cout << row[i] << " "; // cout << grid[i] << " "; } // cout << '\n'; } // cout << grid[(ey - 1) / 2][(ex - 1) / 2] << "\n"; dp[(sy - 1) / 2][(sx - 1) / 2] = 0; for (int y = grid.size() - 1; y >= 0; y--) { for (int x = 0; x < grid[y].size(); x++) { if ((y + 1) <= grid.size() - 1) { if (dp[y][x] != -1) dp[y][x] = dp[y + 1][x]+ abs(grid[y][x] - grid[y + 1][x]); if ((x - 1) >= 0) { if (dp[y + 1][x - 1] != -1) { int second_val = dp[y + 1][x - 1] + abs(grid[y][x] - grid[y + 1][x - 1]); if (y != grid.size() - 1 && x != 0) second_val += adjust_height(grid[y][x], grid[y + 1][x], grid[y][x - 1]); dp[y][x] = my_min(dp[y][x], second_val); // TODO } } } } } for (auto &row : dp) { for (int i = 0; i < row.size(); i++) { // cout << row[i] << " "; } // cout << '\n'; } cout << dp[(ey - 1) / 2][(ex - 1) / 2] + straight_dist << "\n"; return 0; } /* 8 8 1 7 7 1 2 3 2 0 2 1 1 2 1 2 0 0 0 0 0 1 6 8 1 7 6 1 2 3 4 7 6 5 8 9 10 13 12 11 */