Page 163 - MATINF Nr. 1

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 163

deplasa prin livad˘a, de la un pom la fiecare din cei cel mult 4 pomi vecini la care au acces, doar
pe direct , iile paralele cu laturile livezii.

Cerint , ˘a
Cunoscˆand dimensiunile livezii m s , i n, num˘arul de mere c˘azute din fiecare din cei m · n pomi,

coordonatele L, C unde se afl˘a c˘asut , a aricilor, coordonatele celor doi arici s , i codurile lor de
acces, determinat , i:

1. num˘arul X de pomi la care au acces ambii arici;

2. num˘arul Nr al ariciului cˆas , tig˘ator (1 sau 2, corespunz˘ator cu num˘arul de ordine al
ariciului), distant , a minim˘a Dmin pe care o parcurge ariciul cˆas , tig˘ator pentru a ajunge la c˘asut , a
aricilor s , i num˘arul NrM de pomi de unde ar putea pleca ariciul cˆas , tig˘ator astfel ˆıncˆat s˘a
parcurg˘a aceeas , i distant , ˘a minim˘a pˆan˘a la c˘asut , a aricilor.

Date de intrare
Fis , ierul de intrare arici.in cont , ine:

- pe prima linie un num˘ar natural p; pentru toate testele de intrare, num˘arul p poate avea
doar valoarea 1 sau 2;

- pe a doua linie dou˘a numere naturale nenule m, n, separate prin cˆate un spat , iu, cu
semnificat , iile din enunt , ;

- pe linia a treia dou˘a numere naturale nenule L, C, separate prin cˆate un spat , iu, cu
semnificat , iile din enunt , ;

- pe liniile a patra s , i a cincea cˆate trei numere naturale reprezentˆand coordonatele pomilor
unde se g˘asesc init , ial cei doi arici (linia, coloana) s , i codul de acces al aricilor: x 1 , y 1 , c 1 , respectiv
x 2 , y 2 , c 2 ;

- pe urm˘atoarele m linii cˆate n numere naturale de exact dou˘a cifre, separate prin cˆate un
spat , iu, reprezentˆand num˘arul de mere c˘azute din fiecare pom al livezii.

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire arici.out se va scrie un singur num˘ar natural, X, repre-
zentˆand num˘arul total de pomi la care au acces ambii arici.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, fis , ierul de ies , ire arici.out va cont , ine numerele naturale Nr, Dmin s , i NrM,
ˆın aceast˘a ordine, separate prin cˆate un spat , iu.

Restrict , ii s , i preciz˘ari

• 2 ≤ m, n, L, C, x 1 , y 1 , x 2 , y 2 ≤ 300

• 11111 ≤ c 1 , c 2 ≤ 99999
• 10 ≤ num˘arul de mere c˘azute din fiecare pom ≤ 99