O rezervaţie de urşi panda, privită de sus, are formă dreptunghiulară şi este compusă din n rânduri identice, iar pe fiecare rând sunt m ţarcuri identice cu baza pătrată. Ţarcurile sunt îngrădite şi sunt prevăzute cu uşi către toate cele 4 ţarcuri vecine. Uşile sunt prevăzute cu câte un cod de acces, ca atare acestea se închid şi se deschid automat. Prin acest sistem, unele ţarcuri sunt accesibile ursuleţilor, iar altele le sunt interzise acestora. În T ţarcuri se găseşte mâncare pentru ursuleţi.
Ursuleţii din rezervaţie poartă câte un microcip care le deschide automat uşile ţarcurilor unde pot intra şi închide automat uşile ţarcurilor interzise. Un ţarc este accesibil ursuleţului dacă ultimele S cifre ale reprezentărilor binare ale codului ţarcului şi ale codului K de pe microcip sunt complementare. (Exemplu: pentru S=8, 11101011 şi 00010100 sunt complementare).
Într-un ţarc este un ursuleţ căruia i s-a făcut foame. Ursuleţul se deplasează doar paralel cu laturile dreptunghiului. Trecerea dintr-un ţarc în altul vecin cu el se face într-o secundă.
Cerinţă
Cunoscând n şi m dimensiunile rezervaţiei, codurile de acces de la fiecare dintre cele n*m ţarcuri, coordonatele celor T ţarcuri cu mâncare, coordonatele ţarcului L şi C unde se află iniţial ursuleţul, codul K al microcipului său şi numărul S, determinaţi:
a) Numărul X de ţarcuri care îndeplinesc proprietatea că ultimele S cifre din reprezentarea binară a codului lor sunt complementare cu ultimele S cifre din reprezentarea binară a codului K purtat de ursuleţ, cu excepţia ţarcului în care se află acesta iniţial.
b) Numărul minim de secunde Smin în care poate ajunge la un ţarc cu mâncare precum şi numărul de ţarcuri cu mâncare nt la care poate ajunge în acest timp minim.
Date de intrare
Fişierul de intrare panda.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua se află linie trei numere naturale n, m şi T separate prin câte un spaţiu, cu semnificaţiile din enunţ. Pe linia a treia se află patru numere naturale nenule L, C, K şi S, separate prin câte un spaţiu, cu semnificaţiile din enunţ. Pe următoarele T linii se află câte două numere naturale reprezentând coordonatele ţarcurilor cu mâncare. Pe următoarele n linii se află câte m numere naturale, separate prin câte un spaţiu, reprezentând codurile de acces la uşile din cele n*m ţarcuri ale rezervaţiei.
Date de ieşire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă.
În acest caz, în fişierul de ieşire panda.out se va scrie un singur număr natural X, reprezentând numărul total de ţarcuri pe care le poate accesa ursuleţul, cu excepţia ţarcului în care se află acesta iniţial.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă.
În acest caz, fişierul de ieşire panda.out va conţine numerele naturale naturale Smin şi nt, în această ordine, separate printr-un spaţiu.
Restricţii
• 2 ≤ n,m ≤ 500
• 1 ≤ S ≤ 8
• 1 ≤ T < n*m
• 0 ≤ K, valorile codurilor ≤ 9999
• Pentru toate testele problemei există soluţie, adică ursuleţul poate ajunge la cel puţin unul dintre ţarcurile cu mâncare.
• Mâncarea se poate găsi şi în zone inaccesibile.
Dacă notăm cu 1 ţarcurile accesibile şi cu 0 cele inaccesibile, obţinem următoarea matrice:
0 1 0 1 1 0
1 0 1 0 1 1
0 0 1 1 1 1
0 1 0 0 1 1
1 1 1 1 1 1
Ursuleţul se află în ţarcul de coordonate (3,5) şi poate ajunge la un singur ţarc cu mâncare, după 6 secunde. Acest ţarc este cel de la coordonatele (5,1) ; drumul parcurs este ;
(3,5)→(4,5) →(5,5) →(5,4) →(5,3) →(5,2) →(5,1)
Atenţie! Pentru acest test se rezolvă doar cerinţa b).