COCI '19 Contest 5 #1 Emacs

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

While playing in his favourite text editor, Daniel decided to draw a picture that was characters high and characters wide. The picture consists solely of characters . and * such that characters * form some non-overlapping rectangles. The rectangles don't even touch each other on their sides or corners.

Help Daniel count the number of rectangles drawn on the picture.

Input

The first line contains two integers and from task description.

Each of the next lines contains characters . or * which represent the picture that Daniel drew.

Output

In a single line you should output the number of rectangles on the picture.

Scoring

In the test cases worth a total of of the points, all rectangles will consist of a single * character.

In the test cases worth additional of the points, it will hold .

Sample Input 1

6 7
***....
***..**
.....**
.***.**
.***...
.***...

Sample Output 1

3

Sample Input 2

3 3
*.*
...
*.*

Sample Output 2

4

Sample Input 3

1 10
.*.**.***.

Sample Output 3

3

• commented on Sept. 2, 2021, 5:20 p.m.

Hi everyone,

As I didn't (and still don't) realy understand this problem, I searched and found the code of a published solution ... unfortunatelly without the expected results :)

Taken the following input:

3 3
***
**.
*..

The returned ouput is:

1

But in my point of view there is not any rectangle because the pattern shaped by the '*' is a triangle not a rectangle. In my understanding of the problem, the following inputs are example of cases that would be associated with an output of 1 :

3 3  3 3  3 3  3 3
***  **.  ...  ...
***  **.  .**  ..*
...  ...  .**  ...

If someone can enlight me, it will be very nice.

Thanx

• commented on Sept. 2, 2021, 7:55 p.m. edited
1. If the input follows the input section, then your program must be able to solve it.
2. If the input does not follow the input section, then your program can do anything (e.g. exit quietly, throw an error, melt the server, etc).
3. Does your example follow the input section? Can Daniel draw this picture?
• commented on Sept. 3, 2021, 4:12 a.m.

In my opinion, yes my examples follow the input section if i use the last of my example : N = 3, M = 3 and the list representation of Daniel's picture is ["...", "..*", "..."] (3 strings made of 3 characters)

My script which is invalidated by the platform can also "isolate" the rectangles with their ID (constraint : the number of rectangle must be < 10). Based upon the first sample input, i detect 3 rectangle (rectangle 1, 2 and 3)

111....
111..22
.....22
.333.22
.333...
.333...
• commented on Sept. 3, 2021, 1:12 a.m.

Please note that the DMOJ administrative staff profusely object to their servers being melted.