Катя та калюжі (puddles)
Одного разу весною Катя задумалася про те, що вона нестерпно хоче поїхати на море. Вона потягнулася до екрану монітору, щоб побачити рекламу відпочинку і… Розлила воду на матрицю розміром M×N. На превеликий жах матриця прямо на очах перетворилася на сушу та водойми. Правда, скупчення води на матриці нерозділене сушею, важко назвати морем, але на калюжу воно дійсно схоже. За одну годину всі клітинки, в яких є вода та суміжні із сушею, висихають, тобто перетворюються на сушу. Таким чином кількість калюж змінюється. Спочатку Катя дуже засмутилася, але потім їй стало цікаво через скільки годин у неї на матриці буде рівно K калюж.
Оскільки Катя не дуже сильний програміст, то цю задачу вона залишає для вас.
Технічні умови
Програма puddles спочатку зчитує зі стандартного пристрою введення (клавіатури) три цілих числа M, N, K (1⩽ M,N ⩽103,1⩽ K ⩽106). Кожен з наступних M рядків буде містити N символів, кожен з яких може бути або d і це означає, що на цьому елементі знаходиться суша, або w – вода. Гарантується, що в матриці Каті, після того як вона розлила воду, є і суша, і вода.
Програма виводить на стандартний пристрій виведення (екран) єдине значення – час, коли в матриці буде рівно K калюж або «No Solution» (без лапок), якщо відповіді не існує.
Приклад
| Введення 1 | Виведення 1 |
|
5 5 3 wwwww wdddw wwdww wwdww wwwww |
No Solution |
| Введення 2 | Виведення 2 |
|
5 9 2 ddddddddd dwwwdwwwd dwwwwwwwd dwwwdwwwd ddddddddd |
1 |