Fișierul intrare/ieșire ce.in, ce.out Sursă Baraj Shumen Vianu juniori 2015
Autor Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in ce.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii