Biến đổi từ vựng Word Ladder: BFS hai đầu (Bidirectional BFS)

Mục tiêu kiến thức

• Hiểu kỹ thuật duyệt BFS hai đầu (Bidirectional BFS): Mở rộng đồng thời từ đỉnh nguồn và đỉnh đích để giảm không gian tìm kiếm từ O(B^D) xuống O(B^D/2).
• Xây dựng cạnh kề động trên xâu: Thay vì so sánh mọi cặp từ (O(N² · L)), thử thay đổi từng ký tự trong 26 chữ cái (O(26 · L)) rồi tra cứu trong bảng băm.

Mô tả bài toán

Cho từ bắt đầu start, từ đích target và một tập từ điển gồm N từ có cùng độ dài L. Mỗi bước biến đổi chỉ được phép thay đổi đúng 1 ký tự và từ mới tạo thành phải nằm trong tập từ điển. Hãy tìm số lượng từ ít nhất trong chuỗi biến đổi từ start đến target (bao gồm cả start và target). Nếu không thể biến đổi, in ra 0.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 5000, 1 ≤ L ≤ 10.
• Thời gian: 1000ms. Bộ nhớ: 256MB.