Fişierul intrare/ieşire:ce.in, ce.outSursăBaraj Shumen Vianu juniori 2015
AutorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

CE (Caracteristică Euler)

Pentru o imagine bidimensională, caracteristica Euler se defineşte ca numărul de regiuni conexe minus numărul de găuri din regiuni. Caracteristica Euler are aplicaţii utile în recunoaşterea şi clasificarea imaginilor. Să considerăm următoarele imagini alb-negru şi caracteristicile lor Euler.

1 regiune conexă
2 găuri
Caracteristica Euler = -1
1 regiune conexă
1 gaură
Caracteristica Euler = 0
1 regiune conexă
0 găuri
Caracteristica Euler = 1
2 regiuni conexe
0 găuri
Caracteristica Euler = 2

Observaţi că, în această problemă, considerăm regiunile pline care se ating pe diagonală ca parte din aceeaşi regiune. În schimb, găurile care se ating doar pe diagonală sunt considerate separate.

Cerinţă

Calculaţi caracteristica Euler pentru un şir de imagini date.

Date de intrare

Fişierul de intrare ce.in conţine pe prima linie numărul de imagini, T. Urmează T teste, fiecare cu următorul format:

  • Pe prima linie apare numărul N, reprezentând înălţimea imaginii.
  • Pe a doua linie apare numărul M, reprezentând lăţimea imaginii.
  • Pe următoarele N linii apar câte M caractere. Fiecare caracter este fie litera mare „X”, reprezentând un pixel negru, fie litera mare „O”, reprezentând un pixel alb.

Date de ieşire

În fişierul de ieşire ce.out se vor tipări T linii. Pe fiecare linie va apărea un singur întreg reprezentând, în ordine, răspunsurile la cele T teste.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 1.000

Exemplu

ce.ince.out
1
4
4
OOOO
OXXO
OXXO
OOOO
1

Explicaţie

Exemplul conţine o singură imagine. Imaginea conţine o singură regiune conexă pătrată, înconjurată de pixeli albi. Caracteristica Euler este 1 regiune - 0 găuri = 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici