#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int x, y;
    int g, h;
    Node(int _x, int _y, int _g, int _h) {
        x = _x; y = _y; g = _g; h = _h;
    }
    int f() const { return g + h; }
};
 
// Hàm so sánh để priority_queue lấy node có f() nhỏ nhất
struct cmp {
    bool operator()(const Node& a, const Node& b) {
        return a.f() > b.f();
    }
};
 
int n, m;
int sx, sy, tx, ty; // start, target
int a[105][105];    // bản đồ: 0 đi được, 1 là vật cản
bool visited[105][105];
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int heuristic(int x, int y) {
    return abs(x - tx) + abs(y - ty); // Manhattan
}
 
int Astar() {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push(Node(sx, sy, 0, heuristic(sx, sy)));
 
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int x = cur.x, y = cur.y;
 
        if (visited[x][y]) continue;
        visited[x][y] = true;
 
        // đến đích
        if (x == tx && y == ty)
            return cur.g;
 
        // duyệt 4 hướng
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (a[nx][ny] == 1) continue;
            if (!visited[nx][ny]) {
                int ng = cur.g + 1;
                int nh = heuristic(nx, ny);
                pq.push(Node(nx, ny, ng, nh));
            }
        }
    }
    return -1; // không tìm được đường
}
 
int main() {
    cin >> n >> m;
    cin >> sx >> sy >> tx >> ty;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
 
    int res = Astar();
    if (res == -1) cout << "Khong tim duoc duong\n";
    else cout << "Do dai duong di ngan nhat: " << res << "\n";
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTm9kZSB7CiAgICBpbnQgeCwgeTsKICAgIGludCBnLCBoOwogICAgTm9kZShpbnQgX3gsIGludCBfeSwgaW50IF9nLCBpbnQgX2gpIHsKICAgICAgICB4ID0gX3g7IHkgPSBfeTsgZyA9IF9nOyBoID0gX2g7CiAgICB9CiAgICBpbnQgZigpIGNvbnN0IHsgcmV0dXJuIGcgKyBoOyB9Cn07CgovLyBIw6BtIHNvIHPDoW5oIMSR4buDIHByaW9yaXR5X3F1ZXVlIGzhuqV5IG5vZGUgY8OzIGYoKSBuaOG7jyBuaOG6pXQKc3RydWN0IGNtcCB7CiAgICBib29sIG9wZXJhdG9yKCkoY29uc3QgTm9kZSYgYSwgY29uc3QgTm9kZSYgYikgewogICAgICAgIHJldHVybiBhLmYoKSA+IGIuZigpOwogICAgfQp9OwoKaW50IG4sIG07CmludCBzeCwgc3ksIHR4LCB0eTsgLy8gc3RhcnQsIHRhcmdldAppbnQgYVsxMDVdWzEwNV07ICAgIC8vIGLhuqNuIMSR4buTOiAwIMSRaSDEkcaw4bujYywgMSBsw6AgduG6rXQgY+G6o24KYm9vbCB2aXNpdGVkWzEwNV1bMTA1XTsKCmludCBkeFtdID0gezEsIC0xLCAwLCAwfTsKaW50IGR5W10gPSB7MCwgMCwgMSwgLTF9OwoKaW50IGhldXJpc3RpYyhpbnQgeCwgaW50IHkpIHsKICAgIHJldHVybiBhYnMoeCAtIHR4KSArIGFicyh5IC0gdHkpOyAvLyBNYW5oYXR0YW4KfQoKaW50IEFzdGFyKCkgewogICAgcHJpb3JpdHlfcXVldWU8Tm9kZSwgdmVjdG9yPE5vZGU+LCBjbXA+IHBxOwogICAgcHEucHVzaChOb2RlKHN4LCBzeSwgMCwgaGV1cmlzdGljKHN4LCBzeSkpKTsKCiAgICB3aGlsZSAoIXBxLmVtcHR5KCkpIHsKICAgICAgICBOb2RlIGN1ciA9IHBxLnRvcCgpOyBwcS5wb3AoKTsKICAgICAgICBpbnQgeCA9IGN1ci54LCB5ID0gY3VyLnk7CgogICAgICAgIGlmICh2aXNpdGVkW3hdW3ldKSBjb250aW51ZTsKICAgICAgICB2aXNpdGVkW3hdW3ldID0gdHJ1ZTsKCiAgICAgICAgLy8gxJHhur9uIMSRw61jaAogICAgICAgIGlmICh4ID09IHR4ICYmIHkgPT0gdHkpCiAgICAgICAgICAgIHJldHVybiBjdXIuZzsKCiAgICAgICAgLy8gZHV54buHdCA0IGjGsOG7m25nCiAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCA0OyBrKyspIHsKICAgICAgICAgICAgaW50IG54ID0geCArIGR4W2tdOwogICAgICAgICAgICBpbnQgbnkgPSB5ICsgZHlba107CgogICAgICAgICAgICBpZiAobnggPCAwIHx8IG55IDwgMCB8fCBueCA+PSBuIHx8IG55ID49IG0pIGNvbnRpbnVlOwogICAgICAgICAgICBpZiAoYVtueF1bbnldID09IDEpIGNvbnRpbnVlOwogICAgICAgICAgICBpZiAoIXZpc2l0ZWRbbnhdW255XSkgewogICAgICAgICAgICAgICAgaW50IG5nID0gY3VyLmcgKyAxOwogICAgICAgICAgICAgICAgaW50IG5oID0gaGV1cmlzdGljKG54LCBueSk7CiAgICAgICAgICAgICAgICBwcS5wdXNoKE5vZGUobngsIG55LCBuZywgbmgpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAtMTsgLy8ga2jDtG5nIHTDrG0gxJHGsOG7o2MgxJHGsOG7nW5nCn0KCmludCBtYWluKCkgewogICAgY2luID4+IG4gPj4gbTsKICAgIGNpbiA+PiBzeCA+PiBzeSA+PiB0eCA+PiB0eTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG07IGorKykKICAgICAgICAgICAgY2luID4+IGFbaV1bal07CgogICAgaW50IHJlcyA9IEFzdGFyKCk7CiAgICBpZiAocmVzID09IC0xKSBjb3V0IDw8ICJLaG9uZyB0aW0gZHVvYyBkdW9uZ1xuIjsKICAgIGVsc2UgY291dCA8PCAiRG8gZGFpIGR1b25nIGRpIG5nYW4gbmhhdDogIiA8PCByZXMgPDwgIlxuIjsKfQo=