• Tạo thêm \(m * n\) đỉnh ảo \(x_1....x_{m * n}\) và \(m * n\) đỉnh \(y_1....y_{m * n}\)
• xét các ô trong bảng, thêm cạnh nối giữa những ô kề nhau.
• thêm cung từ \(ô(i,j)\) đến \(xa(i,j)\) nếu \(a(i,j) <= m*n\)
• thêm cung từ \(xa(i,j)\) đến \(ya(i,j)\)
• thêm cung từ \(ya(i,j)\) đến các \(ô(u,v)\) với \(u * v=a(i,j)\) (Có tối đa \(m * n*log(m*n)\) cung như vậy).
• Sau đó với mỗi truy vấn ta sẽ dùng thuật toán BFS để đi từ \(ô(p_k,q_k)\) đến \(ô(r_k,s_k)\).

Đpt: \(O(k * m*n*log(m*n))\)

Lời giải của BTC cuộc thi