[BFS] – SPOJ PPATH

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

Email 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 *