Đẩy Hộp

Lời giải: Push a Box

Nhận xét quan trọng

Nếu theo dõi cả vị trí của Bessie lẫn vị trí của hộp, không gian trạng thái sẽ là $O(N^2{M}^2)$ — quá lớn với $N,M\le 1500$.

Nhận thấy rằng vị trí chính xác của Bessie không quan trọng, chỉ cần biết Bessie đang ở phía nào của hộp (trên, dưới, trái, phải). Do đó, trạng thái được rút gọn thành: (vị trí hộp, hướng Bessie tiếp cận hộp) — chỉ $O(NM)$ trạng thái.

Thuật toán

Bước 1: Xây dựng đồ thị thành phần liên thông song (Biconnected Components)

Trước khi thực hiện BFS trên trạng thái (hộp, hướng), cần trả lời các câu hỏi:

Nếu hộp đang ở ô $B$, Bessie có thể đi từ phía $d_1$ sang phía $d_2$ của hộp mà không di chuyển hộp không?

Đây tương đương với: có đường đi trong lưới (bỏ ô $B$) từ ô kề $B$ theo hướng $d_1$ đến ô kề $B$ theo hướng $d_2$ không?

Sử dụng biconnected components (thành phần liên thông song): nếu hai đỉnh thuộc cùng một biconnected component, thì có đường đi giữa chúng không đi qua bất kỳ đỉnh khớp nào — nghĩa là có thể đi vòng quanh mà không cần đi qua đỉnh bị chặn.

Cụ thể: với mỗi ô $B$ trong lưới, xây dựng BCC của đồ thị các ô trống (không kể ô $B$). Hai phía của hộp có thể chuyển đổi khi Bessie đi vòng nếu hai ô kề đó thuộc cùng một BCC — điều này trả lời được trong $O(1)$ sau tiền xử lý $O(NM)$.

Bước 2: BFS trên không gian trạng thái

Trạng thái: $(r_B,c_B,d)$ — hộp ở $(r_B,c_B)$, Bessie tiếp cận từ hướng $d\in \{0,1,2,3\}$ (Bắc, Nam, Tây, Đông).

Từ trạng thái $(r_B,c_B,d)$:

• Đẩy hộp: Bessie đẩy hộp theo hướng đối diện với $d$. Hộp dịch sang ô mới $(r_B^{\prime },c_B^{\prime })$; Bessie tiếp cận hộp từ hướng $d$ (giờ cô ở vị trí cũ của hộp). Chuyển trạng thái: $(r_B^{\prime },c_B^{\prime },d)$.
• Đi vòng quanh hộp: Không đẩy hộp, Bessie chuyển sang phía $d^{\prime }$ của hộp. Được phép khi hai ô kề tương ứng thuộc cùng BCC (sau khi bỏ ô $B$). Chuyển trạng thái: $(r_B,c_B,d^{\prime })$.

Thực hiện BFS từ trạng thái ban đầu: hộp ở vị trí B, hướng Bessie tiếp cận tương ứng với vị trí A.

Bước 3: Trả lời truy vấn

Sau BFS, ô $(r,c)$ có thể đạt được nếu tồn tại ít nhất một hướng $d$ sao cho trạng thái $(r,c,d)$ đã được thăm.

Độ phức tạp

• Tiền xử lý BCC: $O(NM)$
• BFS: $O(NM)$ trạng thái, mỗi trạng thái xử lý $O(1)$
• Trả lời truy vấn: $O(1)$ mỗi truy vấn
• Tổng: $O(NM+Q)$