Muallif: __thecrash__
E. Devorbuzar
Sizga o'lchami \(n \times m\) bo'lgan to'g'ri burchakli labirint berilgan. Labirint \(n\) ta qatordan iborat bo'lib, har bir qator \(m\) ta belgidan tashkil topgan. Har bir katak ikkita holatdan biriga ega:
- \(\text{«.»}\) — bo'sh katak (yurish mumkin);
- \(\text{«#»}\) — devor (odatda yurib bo'lmaydi).
Qatorlar \(1\) dan \(n\) gacha (yuqoridan pastga), ustunlar esa \(1\) dan \(m\) gacha (chapdan o'ngga) raqamlangan. \((r, c)\) katak \(r-\)qator va \(c-\)ustunda joylashgan katakni bildiradi.
Siz \((1, 1)\) katakdan sayohatni boshlaysiz va \((n, m)\) katakka yetib borishingiz kerak. Bir qadamda joriy katakdan unga chegaradosh (yuqori, quyi, chap yoki o'ng) katakka o'tishingiz mumkin.
Sizda maxsus kuch bor: sayohat davomida jami ko'pi bilan \(k\) ta devor katagini "buzib", oddiy bo'sh katakka aylantirib, undan o'tishingiz mumkin. Devorni buzib o'tish ham bitta oddiy qadam kabi hisoblanadi (ya'ni devor bo'lgan katakka o'tish ham 1 ta qadam sifatida hisoblanadi, lekin bunday o'tishlar soni \(k\) tadan oshmasligi kerak).
\((1, 1)\) va \((n, m)\) katakchalari har doim bo'sh \(\text{«.»}\) bo'lishi kafolatlanadi.
\((1, 1)\) dan \((n, m)\) gacha yetib borish uchun kerak bo'ladigan eng kam qadamlar sonini toping. Agar hech qanday holatda (ko'pi bilan \(k\) ta devor buzib ham) yetib bo'lmasa, \(-1\) chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda uchta butun son \(n\), \(m\) va \(k\) (\(2 \le n, m \le 300\); \(0 \le k \le \min(n \cdot m,\ 20)\)) — labirintning o'lchamlari va buzish mumkin bo'lgan devorlar sonining chegarasi berilgan.
Keyingi \(n\) ta qatorning har birida \(m\) ta belgidan iborat qator berilgan — labirintning tasviri (\(\text{«.»}\) yoki \(\text{«#»}\)).
Chiquvchi ma'lumotlar
Yagona butun sonni — \((1,1)\) dan \((n,m)\) gacha yetib borish uchun kerak bo'ladigan eng kam qadamlar sonini (yoki bu imkonsiz bo'lsa \(-1\)) chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
3 5 1 ..... ##### ..... |
6 |
2 |
5 5 0 ..... ..... ..... ....# ...#. |
-1 |
3 |
5 5 1 ..... ..... ..... ....# ...#. |
8 |
Izoh
1-Test: O'rtadagi qator to'liq devordan iborat, shuning uchun kamida bitta devorni buzish kerak. Masalan, \((1,1) \to (2,1)\) (devor buzib) \(\to (3,1) \to (3,2)\) \(\to (3,3) \to (3,4) \to (3,5)\) — jami \(6\) ta qadam.
2-Test: \(k=0\) bo'lgani uchun devor buzish mumkin emas, \((5,5)\) katakning ikkala qo'shnisi ham devor bo'lgani sabab uni umuman bosib bo'lmaydi.
3-Test: Endi bitta devor buzish mumkin. \((5,5)\) katakka \((4,3)\) yoki \((3,5)\) orqali kirib, faqat bitta devorni buzish kifoya qiladi — javob Manhetten masofasiga (\(4+4=8\)) teng bo'lib qoladi.