COCI-06 (2006) - Γύρος #2 - 5 (Stol)

View as PDF

Submit solution

Points: 38 (partial)
Time limit: 1.0s
Memory limit: 32M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Stol

Ο Mirko αγόρασε ένα διαμέρισμα και θέλει να καλέσει σε δείπνο όσο το δυνατόν περισσότερους ανθρώπους για να γιορτάσουν με αυτόν. Για αυτό χρειάζεται ένα μεγάλο ορθογώνιο ξύλινο τραπέζι στο οποίο θα καθίσει με τους καλεσμένους του. Ο αριθμός των ατόμων που μπορεί να φιλοξενήσει ένα τραπέζι είναι ίσος με την περίμετρό του (το άθροισμα των μηκών όλων των τεσσάρων πλευρών). Ο Μίρκο θέλει να αγοράσει ένα τραπέζι έτσι ώστε να χωράει στο διαμέρισμά του και όσοι το δυνατόν περισσότεροι άνθρωποι μπορούν να καθίσουν μαζί του για δείπνο. Το τραπέζι πρέπει να τοποθετηθεί έτσι ώστε οι πλευρές του να είναι παράλληλες με τις πλευρές του διαμερίσματος.
Δεδομένης της διάταξης του διαμερίσματος, βρείτε τον αριθμό των ατόμων που μπορεί να προσκαλέσει ο Mirko σε δείπνο.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους R και C (1 \le R,\;S \le 400), τις διαστάσεις του διαμερίσματος.
Κάθε μία από τις ακόλουθες R σειρές περιέχει ακριβώς S χαρακτήρες (χωρίς κενά), είτε ένα ελεύθερο πεδίο ('.') ή ένα αποκλεισμένο ('X').
Ο Mirko μπορεί να βάλει το τραπέζι του μόνο σε ελεύθερα πεδία.

Έξοδος

Εκτυπώστε τον αριθμό των καλεσμένων που μπορεί να προσκαλέσει ο Mirko στο δείπνο αφού αγοράσει το τραπέζι του σε μία γραμμή.

Παραδείγματα

input

2 2
..
..

output

7

input

4 4
X.XX
X..X
..X.
..XX

output

9

input

3 3
X.X
.X.
X.X

output

3

Comments

There are no comments at the moment.