Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2023. december 3.

December 3, 2023, 10:00 AM – December 3, 2023, 3:30 PM

Rectangles

Even though everybody is able to type (mostly) correctly and with the speed of lightning, it is important to remember that there exist other methods to increase our dexterity as well. In this exercise to practice with our hands we need to cut rectangles into smaller parts.
The aim of this task is to cut a rectangle made of the +,- and | characters along the "horizontal" and "vertical" lines and print out the areas of each of the resulting smaller polygons in a decreasing order. An important note is that you need to continue the cutting until each resulting polygon is "uncuttable" and you need to print out the areas of these "uncuttable" polygons. As a help: each input of this exercise was created such that after the cutting each resulting polynomial has either 4 or 6 vertices.

Input

The input consists of three parts:

  • The first line is an n positive integer which gives us the width of the initia rectangle.
  • The second line is an m positive integer which gives us the height of the initia rectangle.
  • The following n lines each contain m characters and describes the initial rectangle. The horizontal lines are symbolized by the - characters (e.g.: -------), the vertical lines are symbolized by the | characters below each other and we use the + character whenever a - and | character meets (so e.g. the corners, see the example). The filler character is the space character.

Output

The output must consist of one line of integers separated by a single space character which tells you the areas (in descending order) of each uncuttable polygons. The area of each polygon is the number of whitespace characters inside it.

Restrictions

  • n and m is at most 100
  • each side of the resulting polygons are at least 3, so there is always at least one - or | character between two + signs.
  • the initial rectangle does not have "holes" in it, so each polygon is connected to an other one.

Example

Input:
  1. 10
  2. 11
  3. +-+-+----+
  4. | | |    |
  5. | | |    |
  6. | | |    |
  7. +-+-+    |
  8. | |      |
  9. | |      |
  10. | |      |
  11. | |      |
  12. | |      |
  13. +-+------+
download as text file Output:
  1. 46 5 3 3
download as text file

Explanation

  1. +-+ x 2 (A=3)
  2. | |
  3. | |
  4. | |
  5. +-+
  6. +-+ x 1 (A=5)
  7. | |
  8. | |
  9. | |
  10. | |
  11. | |
  12. +-+
  13.   +----+ x 1 (A=46)
  14.   |    |
  15.   |    |
  16.   |    |
  17. +-+    |
  18. |      |
  19. |      |
  20. |      |
  21. |      |
  22. |      |
  23. +------+
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024