1473: Малюк Смурф у лабіринті

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 20
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Малюк Смурф у лабiринтi хоче дiстатися Смурфетки i повернутися назад. На своєму шляху вiн буде збирати Смурфiнiки. Лабiринт представлений таблицею розмiром \(m\) x \(n\). Кожна клiтина лабiринту або порожня, або мiстить Смурфiнiку, або камiнь. Малюк Смурф знаходиться у клiтинi (1,1), а Смуртфетка у \((m, n)\). Спочатку малюк рухається направо та вниз, а назад вiн повертається рухаючись налiво та вверх.

Єдине обмеження полягає в тому, що коли Смурф вiдвiдує деякi клiтини в певному рядку протягом усiєї подорожi (вперед i назад), то вiдстань мiж будь-якою парою вiдвiданих ним клiтин для кожного рядка лабiринту не повинна перевищувати \(x\). Вiдстань мiж \((i, j)\) та \((i, k)\) дорiвнює \(|k − j|\). Малюк Смурф також не може вiдвiдати клiтину, яка мiстить камiнь. Знайдiть максимальну кiлькiсть Смурфiнiк, якi зможе зiбрати малюк Смурф на всьому шляху.

Формат вхідних даних

Перший рядок мiстить три цiлi числа: \(m\) - кiлькiсть рядкiв, \(n\) - кiлькiсть стовпцiв i \(x\) - обмеження вiдстанi у рядку.

Далi iдуть \(m\) рядкiв, що описують лабiринт. Кожен рядок мiстить ’.’, ’*’ або ’#’, що позначають порожню клiтинку, Смурфiнiк або камiнь. Клiтинки (1,1) чи \((m, n)\) можуть мiстити камiнь.

Обмеження:

\(1 \le m, n \le 1000\)

\(0 \le x \le 5\)

Формат вихідних даних

Знайдiть максимальну кiлькiсть Смурфiнiкiв, якi зможе зiбрати малюк Смурф на своєму шляху. Якщо з (1,1) неможливо дiйти до \((m, n)\) i повернутися назад, то виведiть -1.

Приклад вхідних даних

3 3 1
...
*.*
...

Приклад вихідних даних

1

Коментарі

Ще немає коментарів.