Катя и лужи (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 |