UCRPC F21 D - Stake Your Claim

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type

Grab the biggest space!

Identify and claim the biggest space before your rivals!

Stake Your Claim is a four player minigame in Super Mario Party, and you can view how the game is actually played here. The game is actually quite simple---a rectangle board is given with boundary edges that divide up the board into four regions. Each player selects a section to claim it, and your goal is to pick the region with the largest area. However, the board gets larger and larger as the game goes on, and in many cases, it is not easy for a human to tell which region is the largest. The goal here is to write a computer program to compute the areas for the four sections.

Input Specification

The first line of the input contains two integers, r and c (0\le r, c\le 10^3), indicating the number of rows and columns of the board.

Then you are given 2r+1 lines, each containing 2c+1 characters. Each character is either a dot . (for empty cells), - (for horizontal edges), | (for vertical edges), and + (for corners). Characters in odd columns and odd rows are walls and do not count for areas. Characters in even columns and even rows are the actual cells that count for areas. You can go to the note for more details on how the areas are counted for the sample input instance.

Output Specification

The output only contains 4 integers, indicating the areas in decreasing order.

Sample Input

5 9
+-----------+-----+
|...........|.....|
|.....+-+.+-+.....|
|.....|.|.|.......|
+---+.|.|.|.+-+...|
|...|.|.|.|.|.|...|
+-+.+-+.+-+-+.+-+.|
|.|.........|...|.|
|.+---------+.+-+.|
|.............|...|
+-------------+---+

Sample Output

13 12 11 9

Exaplanation for Sample Output

The sample input exactly describes the game in the above image. The four sections are:

+-----------+-----+
|A.A.A.A.A.A|B.B.B|
|.....+-+.+-+.....|
|A.A.A|C|A|B.B.B.B|
+---+.|.|.|.+-+...|
|C.C|A|C|A|B|D|B B|
+-+.+-+.+-+-+.+-+.|
|D|C.C.C.C.C|D.D|B|
|.+---------+.+-+.|
|D.D.D.D.D.D.D|B.B|
+-------------+---+

Here the areas for sections A, B, C, and D are 12, 13, 9, 11, respectively. Here we use A, B, C and D to denote the four areas. Here . means empty (no wall between two cells) that doesn't count in area. +, - or | mean walls.

Source of pictures and descriptions: https://www.mariowiki.com/Stake_Your_Claim. You can also find more details about the game from this site.

Scoring

There are 20 test cases, 4 points each.


Comments

There are no comments at the moment.