Нурікабе
Ваше завдання — створити розв'язувач для Нурікабе, головоломки, що визначає бінарність. Гра відбувається на сітці, зазвичай прямокутній (без стандартного розміру), яка містить порожні та пронумеровані клітинки. Ви повинні визначити для кожної клітинки, чи є вона білою (земля) чи чорною (вода), дотримуючись наступних умов. Острів — це максимальна зв'язана область білих клітинок.
Водні області повинні утворювати один зв'язаний регіон. (Усі чорні клітинки повинні бути зв'язані.)
Кожна пронумерована клітинка повинна бути частиною острова.
Кількість клітинок в острові дорівнює числу, яке він містить.
Кожен регіон (острів) білих клітинок (земля) повинен містити рівно одне число.
Два острови не можуть бути з'єднані.
2×2 блоки чорних квадратів не допускаються.
Зверніть увагу, що діагональна суміжність не вважається зв'язаністю. Ви можете бути впевнені, що для кожної головоломки завжди існує унікальне рішення.
Вхідні дані
У вхідних даних кілька тестових випадків. Перша строка кожного тестового випадку містить два числа n, m (3 ≤ n, m ≤ 9), які визначають розміри головоломки, за якими слідують n рядків, кожен з яких містить m символів, включаючи '.' (що позначає порожню клітинку) та 1-значні числа.
Остання строка вхідних даних містить два нульових числа.
Вихідні дані
Вихід для кожного тестового випадку повинен показувати розв'язану головоломку. Позначайте чорні (водні) клітинки символом '#'. Додайте порожній рядок у виході після кожної головоломки.