Thang biến đổi từ vựng

General
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho từ xuất phát $S$, từ đích $T$ (cùng độ dài) và một từ điển gồm $N$ từ tiếng Anh viết thường. Trong mỗi bước, bạn được phép thay đổi đúng một ký tự của từ hiện tại để tạo thành một từ mới nằm trong từ điển.

Hãy tìm số bước biến đổi ít nhất để đi từ $S$ đến $T$.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$ và hai xâu $S, T$.

Dòng thứ hai chứa $N$ xâu ký tự thuộc từ điển, cách nhau bởi dấu cách.

Dữ liệu ra

In ra số bước biến đổi ít nhất, hoặc -1 nếu không thể biến đổi $S$ thành $T$.

Ví dụ
Input Output
5 hit cog
hot dot dog lot cog
4
4 hit cog
hot dot dog lot
-1
Giới hạn
  • $1 \le N \le 5000$
  • Độ dài mỗi từ từ $1$ đến $10$, chỉ gồm chữ cái thường a..z
Draft saved