Programming contests

ECN selejtező programozó csapatverseny, 2018. április 21.

April 21, 2018 10:15 AM – April 21, 2018 3:15 PM

Sheba's Amoebas

After a successful Kickstarter campaign, Sheba Arriba has raised enough money for her mail-order biology supply company. “Sheba's Amoebas” can ship Petri dishes already populated with a colony of those tiny one-celled organisms. However, Sheba needs to be able to verify the number of amoebas her company sends out. For each dish, she has a black-and-white image that has been preprocessed to show each amoeba as a simple closed loop of black pixels. (A loop is a minimal set of black pixels in which each pixel is adjacent to exactly two other pixels in the set; adjacent means sharing an edge or corner of a pixel.) All black pixels in the image belong to some loop.

Sheba would like you to write a program that counts the closed loops in a rectangular array of black and white pixels. No two closed loops in the image touch or overlap. One particularly nasty species of cannibalistic amoeba is known to surround and engulf its neighbors; consequently, there may be amoebas within amoebas. For instance, each of the images in Figure 1 contains four amoebas.


Figure 1: Two Petri dishes, each with four amoebas.

Input Specification

The first line of the input contains two integers m and n (1 ≤ mn ≤ 100). This is followed by m lines, each containing n characters. A '#' denotes a black pixel, a '.' denotes a white pixel. For every black pixel, exactly two of its eight neighbors are also black.

Output Specification

Display a single integer representing the number of loops in the input.

Sample Input 1

  1. 12 12
  2. .##########.
  3. #..........#
  4. #..#...##..#
  5. #.##..#..#.#
  6. #......#.#.#
  7. #....#..#..#
  8. #...#.#....#
  9. #..#...#...#
  10. .#..#.#....#
  11. #....#.....#
  12. #.........#.
  13. .#########..
download as text file

Output for Sample Input 1

  1. 4
download as text file

Sample Input 2

  1. 12 10
  2. .#####....
  3. #.....#...
  4. #..#..#...
  5. #.#.#.#...
  6. #..#..#...
  7. .#...#....
  8. ..###.....
  9. ......#...
  10. .##..#.#..
  11. #..#..#...
  12. .##.......
  13. ..........
download as text file

Output for Sample Input 2

  1. 4
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019