[BFS] – SPOJ PPATH

Link: http://www.spoj.com/problems/PPATH/

Hiểu đề PPATH spoj

Bạn đuợc cho 2 số nguyen tố 4 chữ số. Việc của bạn là tìm số bước ngắn nhất để biến số nguyen tố thứ 1 thành số thứ 2.

Quy định rang trong mỗi bước bạn chỉ đổi được 1 trong 4 chữ số của số thứ 1 để đợợc 1 số nguyen tố mới. Cứ thế tiếp diễn cho tới khi nào thành số thứ 2.

Ví du: 1033  -> 1733  -> 3733 -> 3739  -> 3779 -> 8779 -> 8179. (không được chuyển chữ số đầu tiên thành chữ số 0). Nếu không tìm được thì xuất ra “Impossible”.

Gợi ý giải PPATH spoj

Sử dung BFS và Sieve of Eratosthenes. ( chi tiết mình note trong code bên dưới).

 

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *