Muallif: __thecrash__
E. Aysbergdagi pingvinlar
Vaqt limiti: 1000 ms Xotira limiti: 128 mb
Okeanda ulkan aysberg suzib yuribdi, uning ustida bir guruh pingvin dam olmoqda. Yuqoridan qaraganda aysberg va uning atrofi \(n \times m\) o'lchamli jadval ko'rinishida bo'ladi. Har bir katak muz ('#'), suv ('.') yoki ustida pingvin turgan muz ('P') bo'lishi mumkin. Jadvalning tashqarisi butunlay okean suvi.
Havo isib bormoqda. Har kecha suv bilan qo'shni bo'lgan barcha muz kataklari bir vaqtda erib, suvga aylanadi. \((i, j)\) katakning qo'shnilari \((i-1, j)\), \((i+1, j)\), \((i, j-1)\) va \((i, j+1)\) kataklardir. Jadvaldan tashqaridagi qo'shnilar suv hisoblanadi. Muz o'rtasidagi ko'llar ham suv bo'lib, muzni eritadi. Ustida pingvin turgan katak ham oddiy muz kabi eriydi va shu kechada pingvin suvga sakraydi.
Eng oxirgi pingvin nechanchi kechada suvga tushishini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n, m \le 1000\)) jadval o'lchamlari.
Keyingi \(n\) ta qatorning har birida \(m\) ta belgi: '#', '.' yoki 'P'. Jadvalda kamida bitta 'P' borligi kafolatlanadi.
Chiquvchi ma'lumotlar
Eng oxirgi pingvin suvga tushadigan kecha raqamini chiqaring. Kechalar \(1\) dan boshlab sanaladi.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 6 ...... .####. .#PP#. .####. ...... |
2 |
| 2 |
1 1 P |
1 |
| 3 |
7 7 ####### ####### ###P### ####### ###.### ####### ####### |
2 |
Izoh
Birinchi misolda birinchi kechada pingvinlarni o'rab turgan muz halqasi eriydi, ikkinchi kechada pingvinlar turgan kataklar ham eriydi.
Ikkinchi misolda yagona katak okean bilan qo'shni, shuning uchun u birinchi kechadayoq eriydi.
Uchinchi misolda pingvin \((3, 4)\) katakda turibdi va aysberg chetidan uch katak uzoqda. Lekin \((5, 4)\) katakda kichik ko'l bor. Birinchi kechada ko'l bilan qo'shni \((4, 4)\) katak eriydi, ikkinchi kechada esa pingvin turgan katak ham eriydi.