Sürətli Axtarış#1816
Polis dəstəsi bəzən bir neçə məkanı mümkün qədər tez axtarmalı olur, amma bunun üçün yalnız azsaylı əməkdaşları olur. Şəkil 1 və 2-də belə vəziyyətlər üçün sxemlər göstərilmişdir. Axtarılmalı olan məkanlar böyük hərflərlə işarələnib. hərfi ilə işarələnmiş məkan ümumi başlanğıc nöqtəsidir. Bəzi məkanlar yollarla birləşdirilib. Hər yolun keçilməsi bir vahid vaxt aparır; məkanların özü baxışla axtarıldığı üçün əlavə vaxt tələb etmir.
Şəkil 1-i nəzərdən keçirək. Əgər və ya daha çox polis olarsa, axtarış yalnız bir vaxt vahidi çəkir. Müxtəlif əməkdaşlar AB, AC və AD yolları ilə gedirlər. Əgər iki polis olarsa, tam axtarış iki vaxt vahidi çəkir. Məsələn, biri ABC, digəri isə AD yollarını gedə bilər.
Şəkil 2-ni nəzərdən keçirək. Əgər polis olsaydı, onlar ABC, ABD və AEAF yollarından istifadə edərək vahid vaxt sərf edərdilər. polis ilə isə ABCBD və AEAF yollarını gedərək vahid vaxt sərf edərdilər.
Bunlar əl ilə asanlıqla həll edilə bilən sadə nümunələrdir. Daha mürəkkəb vəziyyətlərdə proqramlaşdırma bacarığınıza ehtiyac var.
Daxil olan məlumatlar -dən -ə qədər verilmiş məlumat dəstələrindən və yalnız olan sətrdən ibarətdir.
Hər məlumat dəsti bir sətdir və əvvəlcə boşluqla ayrılmış müsbət tam ədədlər olan gəlir. Burada – axtarılmalı məkanların sayı, – polis əməkdaşlarının sayı, – birləşdirici yolların sayı. Məhdudiyyətlər: 2 \leq s \leq 10, 1 \leq n \leq 4, və p \leq 20. Sətrin davamında ədəd böyük hərf cütlüyü (hər biri boşluqla ayrılmış), məkanlar arasında olan yolları göstərir. Məkanlar ilk böyük hərflə işarələnir. Bütün məkanlar birləşdirici yollar ardıcıllığı ilə bir-birilə əlaqəlidir. Hər bir cüt hərf yalnız bir dəfə verilir və əlifba ardıcıllığında yazılmışdır.
Hər məlumat dəsti üçün, məkanından başlayan polis əməkdaşı üçün minimum axtarış vaxtını göstərən bir sətir çap edin.
Alqoritminiz haqqında diqqətli olun, əks halda həll uzun çəkə bilər.
Nümunə giriş məlumat dəstələri müzakirə olunan ssenarilərə uyğundur.
Nümunə 1