Codeforces Beta Round 87 (Div. 2 Only) |
---|
Закончено |
Давным давно на клетчатом поле размера n × m жили поросята и волки. Каждая клетка поля либо была пуста, либо содержала одного поросенка, либо содержала одного волка.
Поросенок и волк считаются соседями, если клетки, на которых они расположены, имеют общую сторону. Поросята боятся волков, поэтому каждый поросенок имеет не более одного соседа-волка, но волк может иметь сколько угодно соседей-поросят.
Поросята и волки живут мирно уже несколько лет. Но сегодня волки проголодались. Каждый волк выбирает одного соседа-поросенка (если такие имеются) и съедает его. Этот процесс не повторяется, то есть в итоге каждый волк может съесть не более одного поросенка. Как только волк съедает поросенка, этот поросенок исчезает, и никакой другой волк не может его съесть повторно.
Какое наибольшее количество поросят могут съесть волки?
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 10) — количество строк и столбцов в клетчатом поле, соответственно. Далее следует n строк по m символов в каждой — описание поля. «.» обозначает пустую клетку. «P» обозначает клетку, содержащую поросенка. «W» обозначает клетку, содержащую волка.
Гарантируется, что каждый поросенок имеет не более одного соседа-волка.
Выведите одно целое число — максимальное число поросят, которое могут съесть волки.
2 3
PPW
W.P
2
3 3
P.W
.P.
W.P
0
В первом примере волки съедают двух поросят. Один из возможных способов это сделать:
Название |
---|