Nhận xét: Xem mỗi ô trong mê cung là ~1~ đỉnh của đồ thị, với mỗi ô ~(i, j)~ chúng ta xây cạnh đến các ô mà từ ~(i, j)~ có thể đến trong ~1~ bước di chuyển. Nếu đồ thị mà mọi cạnh có chung trọng số thì có thể sử dụng thuật toán BFS để tìm đường đi ngắn nhất giữa ~2~ đỉnh, dễ thấy đồ thị trong bài thỏa mãn điều kiện trên với trọng số chung là ~1~. Vậy ta chỉ cần dựng được đồ thị thì có thể giải quyết được bài toán.

Tuy nhiên, độ phức tạp của thuật toán BFS là ~O(n+m)~ với đồ thị ~n~ đỉnh ~m~ cạnh dẫn đến chúng ta cần chứng minh rằng số cạnh đủ nhỏ để chạy BFS trong ~1~ giây. Nếu bạn không tỉnh táo sẽ bị vướng ở bước này.

Chứng minh số cạnh trên đồ thị ~\leq~ ~8\times N \times M~:

• Nếu ô ~(i, j)~ không phải cột đá thì có tối đa:

~4~ cạnh từ các cột đá gần nhất ở mỗi hướng Đông Tây Nam Bắc đến ô ~(i, j)~

~4~ cạnh từ ~(i, j)~ đến các ô ~(i−1, j), (i, j+1), (i+1, j), (i, j−1)~

• Nếu ô ~(i, j)~ là cột đá thì có tối đa:

~4~ cạnh từ ô ~(i, j)~ đến các cột đá gần nhất ở mỗi hướng Đông Tây Nam Bắc

• Do mê cung gồm ~N \times M~ ô thuộc ~2~ trường hợp trên, hiển nhiên đồ thị có không quá ~8 \times N \times M~ cạnh