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


Submit solution


Points:30
Time limit:2.0s
Python 34.0s
java84.0s
Memory limit:500M
Python 3500M
java8500M
Author:

Problem types

Малюк Смурф у лаб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 <= m, n <= 1000

0 <= x <= 5

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

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

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

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

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

1

Comments

There are no comments at the moment.