LearnToCP
Prijavi se
Navigacija
PočetnaRoad-mapaProblemiO Nama
Teorija
Takmičarsko Znanje
Izbor Radnog Okruženja (IDE)
Osnove
Tvoj Prvi ProgramTipovi podataka, Unos i IzlazC++ sintaksaModuloFunkcijeVektoriMatriceVremenska Složenost Algoritma
Sortiranje
SortiranjeSortiranje PrebrojavanjemRadix Sort
Tehnike Optimizacije
Dva PokazivačaZbir brojeva od 1 do nZbir PrefiksaBinarna PretragaPohlepni AlgoritmiFunkcije Binarne PretrageBinarna Pretraga po RešenjuPodeli, pa Vladaj
Binarni Brojevi
Binarni BrojeviBrojevi u koduOperacije nad BitovimaBitmaske
Matematika
Binarno StepenovanjeProsti BrojeviRastavljanje na proste činioceNZD i NZSEratostenovo SitoModifikovano Sito
Strukture Podataka
Niske (Stringovi)StekRedMapeSkupovi (Set)Red sa PrioritetomKorišćenje Proizvoljnih KriterijumaSegmentna StablaFenvikova StablaSparse TabeleDisjunktni Skupovi
Kombinatorika
Pravilo SabiranjaPravilo MnoženjaKombinatorni ObjektiPrincip Uključenja Isključenja
Geometrija
Osnove GeometrijeVektoriVektorski i Skalarni ProizvodLinijePoligoniUgloviTačka u PoligonuRastojanja i Tačke PresekaKonveksni OmotačKrugovi
Rekurzija
PokazivačiRekurzijaGenerisanje Kombinatornih Objekata
Dinamičko Programiranje
O DP-uDP nad StablimaDP nad BitmaskamaDP nad brojevima
Teorija Grafova
GrafoviDFS i BFSNajkraći PuteviStablaTopološko SortiranjeDajkstrin AlgoritamMinimalna Razapinjuća StablaAlgoritmi Najkraćih Puteva
Napredna Teorija Grafova
Dvostruka PovezanostJako Povezane KomponenteBipartitni GrafMaksimalni Protok u GrafuFord-Fulkersonov AlgoritamDualnost Protoka i Minimalnog PresekaTeško-Laka DekompozicijaCentroidna Dekompozicija
Napredne Strukture Podataka
2D i 3D Segmentna StablaLenjo PropagiranjeImplicitna Segmentna StablaPerzistentna Segmentna StablaNajbliži Zajednički PredakTrieBalansirana Binarna Stabla PretrageMoov Algoritam

Ostrva

EasyProblem #52
VremeMemorijaUlazIzlaz
1 s64 MBstdinstdout

Ovde postoji graf, iako ti niko nije dao nijednu granu.

Satelit je snimio deo okeana i podelio ga na mrežu od n vrsta i m kolona. Svako polje na snimku je ili kopno, oznaka #, ili voda, oznaka ..

Ostrvo je skup polja kopna po kojima možeš da pređeš a da ne pokvasiš noge, koračajući samo gore, dole, levo i desno. Dva polja kopna koja se dodiruju samo temenom nisu na istom ostrvu, jer se dijagonalno ne sme koračati.

Prebroj ostrva na snimku i izmeri koliko je veliko najveće.

Ulaz

U prvoj liniji ulaza nalazi se ceo broj t - broj test primera.
U prvoj liniji svakog test primera su brojevi n i m - broj vrsta i broj kolona snimka.
U narednih n linija nalazi se po m karaktera, # ili ., koji opisuju jednu vrstu snimka.

Izlaz

Za svaki test primer ispiši u posebnoj liniji dva broja - koliko ostrva ima na snimku i od koliko se polja sastoji najveće. Ako je na snimku samo voda, ispiši 0 0.

Primer

Input
1
4 6
#..##.
##..#.
....#.
.##..#
Output
4 4

Ostrva ima četiri, a najveće je ono uz desnu stranu gornjeg dela snimka, od 4 polja. Obrati pažnju na usamljeno polje u donjem desnom uglu: sa ostrvom iznad sebe dodiruje se samo temenom, pa se broji kao zasebno ostrvo.

Ograničenja

1≤t≤1000
1≤n,m≤200
zbir svih n⋅m nije veći od 105

Pošalji svoje rešenje

Prijavi se da pošalješ rešenje i pratiš svoj napredak.

Prijavi se