King's Path

limit = 10^9
mark = set
dist = map
dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]

def calc(x, y):
    return x * limit + y

def bfs():
    q = queue
    s = calc(x0, y0)
    q.add(s)
    dist[s] = 0

    while q not empty:
        u = q.front
        q.pop
        x = u div limit
        y = u mod limit

        for i = 0 to 7:
            newX = x + dx[i]
            newY = y + dy[i]
            v = calc(newX, newY)
            if (0 <= newX < limit and 0 <= newY < limit and v in mark):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    if v == calc(x1, y1):
                        return dist[v]
                    q.add(v)
    return -1

read(x0, y0, x1, y1)
x0 -= 1, y0 -= 1, x1 -= 1, y1 -= 1
mark.add(calc(x0, y0))
mark.add(calc(x1, y1))

read(n)

for i = 1 to n:
    read(r, a, b)
    r -= 1, a -= 1, b -= 1
    for j = a to b:
        mark.add(calc(r, j))

print(bfs())

ĐPT: O(V * logV)
V là số lượng ô đi được