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 dărâmat conduce la un cost de p unităţi monetare.
Cerinţă
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 şef, iar pe linia a doua numărul minim de ziduri dărâmate.
Restricţii
1 < n < 101
0 < p < 101
Nu se acordă punctaje parţiale.
Exemple
ziduri.in
ziduri.out
Explicaţii
4 3
9 1 1 0
12 5 5 1
1 5 5 4
4 6 12 0
8
1
Configuraţia birourilor redacţiei (zidurile sunt marcate cu linie îngroşată)
