Un ziar are redacția la etajul unei clădiri. Acest etaj de formă pătratică este alcătuit numai din camere de aceeași dimensiune și de formă pătratică. Pentru un etaj cu 4×4 camere avem configurația:
Unele dintre zidurile camerelor lipsesc. Directorul și redactorul șef au fiecare biroul în camere separate. Directorul are biroul în camera de pe linia 1 și coloana 1, iar redactorul șef în camera de pe ultima linie și ultima coloană. Deplasarea între două camere vecine se poate face numai dacă ele nu au zid despărțitor. Pentru a mări viteza de deplasare între birourile directorului și redactorului șef se ia decizia ca unele ziduri să fie desființate. Un studiu făcut de departamentul administrativ arată că deplasarea între două camere fără zid conduce la un cost de o unitate monetară, iar deplasarea între două camere care au avut zid și a fost darâmat conduce la un cost de p unități monetare.
Cerinta
Determinați costul minim al unei deplasări de la camera directorului la camera redactorului șef. Dintre toate deplasările de cost minim, determinați numărul minim de ziduri ce trebuie dărâmate într-o astfel de deplasare.
Date de intrare
Fișierul de intrare ziduri.in conține pe prima linie n (numărul de camere de pe o linie, respectiv coloană) și p, costul trecerii de la o cameră la alta între care s-a dărâmat zidul despărțitor; cele două numere fiind separate printr-un spațiu. Pe următoarele n linii se află câte n numere naturale din mulțimea {0,1,…,15} separate prin câte un spațiu. Aceste numere naturale transformate în baza 2 (pe 4 biți) ne dau informații despre existența zidurilor în jurul camerii (1 pentru zid și 0 în caz contrar). De exemplu dacă un astfel de număr are reprezentarea abcd în baza 2, atunci a este pentru zidul dinspre vest, b pentru cel din nord, c pentru cel din est, iar d pentru cel din sud.
Date de ieșire
Fișierul de ieșire ziduri.out va conține pe prima linie costul minim deplasării de la director la redactorul sef, iar pe linia a doua numărul minim de ziduri dărâmate.
Restricții și precizări
1 < n < 1010 < p < 101- Nu se acordă punctaje parțiale.
Exemplu
ziduri.in
4 3
9 1 1 0
12 5 5 1
1 5 5 4
4 6 12 0
ziduri.out
8
1
Explicație
Configurația birourilor redacției (zidurile sunt marcate cu linie îngroșată)
