- Zajęcia w szkołach
- Informatyka i Ty
- O portalu
- Mapa portalu
D - Decision
Time limit: 2 s
In a galaxy not so far away, in a time where men were real men, women were real women, and small furry creatures from Alpha Centauri were real small furry creatures from Alpha Centauri, an astronom called Mr. Gorsky discovered a small inhabited planet. After an initial enthusiasm (yes, we are not alone!), all the living Nobel Peace Prize winners gathered in one place, formed a committee, and discussed options of invading the planet. Long story short, in order to decide on this important topic, they need to know the number of the cities on the remote planet.
The quality of photos delivered by Mr. Gorsky were unfortunately quite bad: on a rectangular grid, each grid element was either blank (no city there) or (partially) dark, which meant a city or a part of it. If two dark parts share a common edge, they are a part of the same city. The committee then said plainly: ``You have to count the number of the cities. Good luck, Mr. Gorsky''.
An example map containing three cities is presented below.
Multiple Test Cases
The input contains several test cases. The first line of the input contains a positive integer , denoting the number of test cases. Then test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.
Single Instance Input
The first line of an input instance contains two integers and , the photo dimensions, such that . The following lines contain the description of the photo. Each line contains characters from the set encoding the grid elements in the following way:
Single Instance Output
For each input instance, your program should output one line containing the number of cities on a given map.
4 1 2 DD 2 2 FB DF 2 3 FAA AFB 4 4 AACB CAFD AFCE AACA
2 1 2 6
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.