COCI '13 Contest 2 #2 Misa

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 32M

Problem type

A nice part of the Roman Catholic Mass is the rite of peace when people shake hands with their neighbours and say "peace be with you". Mirko has found a way to turn this ritual into his own favour.

Inside the church, there are $R$ ~R~ rows of benches where each row can hold a capacity of $S$ ~S~ people. We can imagine the seating order as a matrix sized $R \times S$ ~R \times S~ where each element represents either a person or an empty seating space. Let us assume that each person shakes hands with their neighbours. That means that the neighbours are located in one of the eight neighbouring elements (if such element exists):

$\text{[math]}$

A seating order of the people inside the church has been given before Mirko enters. Mirko is, of course, late for the morning Mass and will sit in an empty space so that he shakes hands with as many people as he can. If there are no empty seats left, Mirko will simply give up on the idea and go to the evening Mass instead. We can assume that nobody enters the church after Mirko.

Calculate the total number of handshakes given during the morning Mass.

Input

The first line of input contains positive integers $R$ ~R~ and $S$ ~S~ $(1 \le R, S \le 50)$ ~(1 \le R, S \le 50)~ as stated in the text. Each of the following $R$ ~R~ lines contains $S$ ~S~ characters. These $R \times S$ ~R \times S~ characters represent the seating order. The character . represents an empty place and the character o represents a person.

Output

The first and only line of output should contain the required number of handshakes.

Scoring

In test data worth 20% of total points, $R$ ~R~ will be 1.

In test data worth 20% of total points, $R$ ~R~ will be 2.

In test data worth 20% of total points, the church will be full, meaning all seats will be taken.

Sample Input 1

2 3
..o
o..

Sample Output 1

Explanation for Sample Output 1

Mirko will sit in a way that he can shake hands with both persons, which gives us the two possibilities:

.oo   ..o
o..   oo.

Sample Input 2

2 2
oo
oo

Sample Output 2

Comments

0

jberrycoding_1987 commented on Sept. 15, 2024, 7:44 p.m.

In the second example, 4 seats have been filled before Mirko arrives which means that, based on the problem specification, Mirko would choose to attend the following Mass. Shouldn't the output be 0? Even if Mirko was to shake hands with those present at most it would be 4 people, so how it is 6? Thank you to anyone who can explain this.

0

Howard0725 commented on Sept. 18, 2024, 2:36 a.m. ← edit 2 →

There are two situations: Availabe and unvailable seating places. Sample 2 is the situation of unvailable seating places. Connect all dots, and there are six lines.