G - Gul de Crack

Time limit: 1s Memory limit: 128MB Input: Output:

Cerință

Avem la dispoziție o tablă de șah de N×MN \times M.

Unele celulte sunt blocate, pe restul celulelor putem pune cai.
Care este numărul maxim de cai pe care îi putem plasa astfel încât să nu se atace între ei?

Calul se mișcă după cum se poate observa:

Date de intrare

Pe prima linie se află numerele NN și MM.
În continuare urmează tabla de șah sub forma unei matrice de caractere cu # căsuță ocupată și . căsuță liberă.

Date de ieșire

Numărul maxim de cai.

Restricții și precizări

  • 1N×M50001 \leq N \times M \leq 5000
  • Pentru 60 de puncte 1N×M3001 \leq N \times M \leq 300
  • Toate testele sunt grupate!\textbf{Toate testele sunt grupate!}

Exemplu

stdin

5 4
#...
.#..
###.
#..#
.###

stdout

6

Log in or sign up to be able to send submissions!