Localitatea Târgovişte este în plină modernizare. Primăria decide să inventarieze toate clădirile din oraş pentru a renova faţadele acestora. În acest sens analizează harta oraşului şi constată că toţi pereţii sunt aşezaţi doar pe direcţia Nord Sud sau Est Vest. Pereţii vizibili de către turişti sunt doar aceia la care se poate ajunge din exteriorul oraşului prin deplasarea pe cele două direcţii date, în oricare din cele 4 sensuri (N, E, S, V). Harta oraşului este întocmită pe un caroiaj format din pătrate cu latura 1.
Cerinţă
Cunoscându-se harta oraşului, determinaţi lungimea pereţilor vizibili ce urmează a fi zugrăviţi.
Date de intrare
Fişierul de intrare pereti.in are pe prima linie dimensiunile m (numărul de linii), n (numărul de coloane) ale hărţii. Pe fiecare dintre următoarele m linii există n numere naturale de la 0 la 15, separate prin câte un spaţiu, cu semnificaţia:
- reprezentarea binară a numărului pe 4 cifre semnifică, începând de la stânga spre dreapta, existenţa unui perete spre direcţiile N, E, S, V. (1- există perete, 0 – nu există perete, explicaţii în figura de mai jos).
De exemplu, valoarea 13 se reprezintă în binar 1101, deci în mod corespunzător, de la stânga spre dreapta, vom avea pereţi spre N, E şi V.
Date de ieşire
Fişierul de ieşire pereti.out va conţine pe prima linie numărul natural k reprezentând lungimea pereţilor ce vor fi zugrăviţi.
Restricţii
1 ≤ m, n ≤ 100
Pereţii aflaţi la marginea hărţii sunt pereţi vizibili.
Datele de intrare sunt considerate corecte.
Exemple
pereti.in
pereti.out
Explicaţii
5 4
0 6 13 1
4 15 5 1
0 14 7 1
4 15 9 0
0 12 5 7
22
Pentru poziţile (5, 2) şi (5, 3) peretele dintre ele va fi zugrăvit pe ambele feţe.
Peretele dinspre Nord al poziţiei (1,3) este perete exterior, chiar dacă se află pe marginea hărţii.
