Fișierul intrare/ieșire | ce.in, ce.out | Sursă | Baraj Shumen Vianu juniori 2015 |
---|---|---|---|
Autor | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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.