Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Life Saving Algorithm

By darkprinx · Limits 1s, 512 MB

Recently flood has vastly affected some regions of the country. So many people are helpless and suffering. They are in need of help. As you are very kind hearted person, you want to send yours helps to the affected areas.

You collected a 2D grid map of N x N size which shows the flood status of the country. The grid represents the following –

  • ‘*’ character indicates dry land areas
  • ‘#’ character indicates flood affected areas
  • ‘.’ character indicates visiting route

Any two flood affected grids are marked as same area if those share horizontal, vertical or diagonal grids. On the other hand, any two dry land grids marked as same area if those share horizontal and vertical grids. A shared grid of flood affected area and dry land area will be counted as different area.

A dry land will be marked as in danger zone of flood if it shares horizontal, vertical or diagonal grid with any flood affected area.

To send help you want to know the total flood affected areas and total areas that might be in danger zone of flood. You can assume to move through any types of grid in the map.

Input

The input will start with a test case T <=10 . Each test case will take the size N<=500 of the map followed by the N x N grid input.

Output

For each test case print the case number, total flood affected areas and total areas in danger zone. Follow the output format in sample output.

Sample

InputOutput
2

3
...
.#*
.*.

8
..****..
...###..
.......
........
........
...##...
..***...
........
Case 1: 1 2
Case 2: 2 2


Discussion
Statistics

75% Solution Ratio

divby0Earliest, Aug '17

aaman007Fastest, 0.1s

Khayrul_34Lightest, 393 kB

minhazmirazShortest, 1257B

Submit

Login to submit