Hướng dẫn giải của Đẩy Hộp

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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 \leq 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 (N M)$ 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 (N M)$ .

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}^{'}, c_{B}^{'})$ ; 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}^{'}, c_{B}^{'}, d)$ .
Đi vòng quanh hộp: Không đẩy hộp, Bessie chuyển sang phía $d^{'}$ 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^{'})$ .

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 (N M)$
BFS: $O (N M)$ 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 (N M + Q)$

Bình luận

Không có bình luận tại thời điểm này.