Kilid Nümunəsi

Telefonların bəzilərini kilidləmək üçün istifadə olunan üsullardan biri kilid naxışıdır. Telefonunuzu açmaq üçün bir neçə nöqtədən ibarət olan bir şəbəkədə gizli bir naxış çəkməlisiniz. Bu naxış, nöqtələri birləşdirən xətt seqmentlərindən ibarət olacaq.

Telefonunuzun naxış şəbəkəsi hər sırada üç nöqtə olan dörd sıradan ibarətdir. Soldakı şəkil şəbəkənin təsviridir və hər nöqtə X və Y koordinatları ilə 2D müstəvi kimi modelləşdirilə bilər. Məsələn, yuxarı sol nöqtə (1,4) və aşağı sağ nöqtə (3,1)-dir. Sağdakı şəkil isə etibarlı bir naxışdır və bu nöqtələri bu ardıcıllıqla birləşdirir: (3,4) (2,4) (1,2) (2,1) (2,2) (3,2) (3,1) (1,3).

Etibarlı bir naxışın aşağıdakı xüsusiyyətləri var:

1. Naxış, ilk dəfə toxunduğu nöqtələrin ardıcıllığı ilə təmsil edilir (naxışı çəkmə ardıcıllığı ilə eyni qaydada). (1,1)-dən (2,2)-yə gedən bir naxış, (2,2)-dən (1,1)-ə gedən bir naxışla eyni deyil.

2. Naxış təmsilindəki hər iki ardıcıl nöqtə A və B üçün, əgər A və B-ni birləşdirən xətt seqmenti başqa nöqtələrdən keçirsə, bu nöqtələr də ardıcıllıqda olmalı və A və B-dən əvvəl gəlməlidir. Əks halda naxış etibarsız olacaq. Məsələn, (3,1) ilə başlayıb sonra (1,3) ilə davam edən bir naxış təmsili etibarsızdır, çünki seqment (2,2)-dən keçir və bu nöqtə (3,1)-dən əvvəl naxış təmsilində görünməyib. Bu naxışın düzgün təmsili (3,1) (2,2) (1,3)-dür. Amma (2,2) (3,2) (3,1) (1,3) naxışı etibarlıdır, çünki (2,2) (3,1)-dən əvvəl görünür.

3. Naxış təmsilində eyni nöqtəni bir dəfədən çox qeyd etmirik, hətta naxış bu nöqtəyə başqa etibarlı bir seqment vasitəsilə yenidən toxunsa belə. Naxışdakı hər bir seqment əvvəllər toxunulmamış bir nöqtədən başqa bir nöqtəyə getməlidir və naxışda artıq görünmüş bəzi nöqtələrdən keçə bilər.

4. Bir naxışın uzunluğu, naxış təmsilindəki hər iki ardıcıl nöqtə arasındakı Manhattan məsafələrinin cəmidir. (X_1,Y_1) və (X_2,Y_2) nöqtələri arasındakı Manhattan məsafəsi |X_1-X_2|+|Y_1-Y_2|-dir (burada |X| X-in mütləq dəyərini ifadə edir). Yuxarıdakı şəkildəki naxışın uzunluğu: 1 + 3 + 2 + 1 + 1 + 1 + 4 = 13-dür.

5. Bir naxış ən azı iki nöqtəyə toxunmalıdır.

Təəssüf ki, telefonunuzun naxışını unutmusunuz, amma naxışın uzunluğunu və naxışa toxunmadığına əmin olduğunuz S nöqtələr dəstini xatırlayırsınız (naxışın toxunub-toxunmadığına əmin olmadığınız nöqtələr S-də deyil). Xatırladığınız şeyləri təmin edən bütün etibarlı naxışları sınamağa qərar verdiniz. Bunu etməzdən əvvəl, sizin üçün fərqli etibarlı naxışların sayını hesablayan bir proqram yazmalısınız.