Fişierul intrare/ieşire:hashtag.in, hashtag.outSursăAlgoritmiada 2015 Runda 3
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hashtag

Formal, un hashtag de dimensiune N x M este o matrice binară care îndeplineşte următoarele condiţii:

Există indicii (indexaţi de la 0) L1 L2 L3 L4 C1 C2 C3 C4 cu următoarele proprietăţi:

1 ≤ L1 ≤ L2
L2 + 2 ≤ L3 ≤ L4 ≤ N - 2
1 ≤ C1 ≤ C2
C2 + 2 ≤ C3 ≤ C4 ≤ M - 2
Celula (i, j) va fi egală cu caracterul '#' dacă şi numai dacă i este în intervalul [L1, L2] sau în intervalul [L3, L4], iar j este în intervalul [C1, C2] sau în intervalul [C3, C4].

Cu alte cuvinte, un hashtag este compus din două bare verticale şi două bare orizontale care nu au neaparat grosime egală. De-asemenea, din relaţiile de mai sus putem observa că două bare paralele nu se pot atinge, iar cele patru colţuri ale matricei nu pot face parte niciodată din hashtag.

Dându-se o matrice de dimensiuni N x M cu caractere din mulţimea {'.', '#'}, care este numărul minim de celule din matrice care trebuie schimbate încât matricea să devină hashtag?

Date de intrare

Fişierul de intrare hashtag.in va conţine pe prima sa linie numerele N şi M. Fiecare din următoarele N linii va conţine un şir de M caractere, fiecare din acestea fiind egal cu '.' sau cu '#'.

Date de ieşire

În fişierul de ieşire hashtag.out se va afla un număr întreg reprezentând numărul minim de celule care trebuie schimbate pentru a obţine un hashtag.

Restricţii

  • 5 ≤ N, M ≤ 30

Exemplu

hashtag.inhashtag.out
7 7
..##.#.
#######
.##..#.
#######
..##.#.
..#..#.
.#.#.#.
5

Explicaţie

Pentru hashtagul rezultat indicii vor fi C1 = 2, C2 = 3, C3 = 5, C4 = 5, L1 = 1, L2 = 1, L3 = 3, L4 = 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?