Bizga \(n \times m\) o'lchamli labirint berilgan. Boshlang'ich nuqta \((1, 1)\), oxirgi manzil esa \((n, m)\). Labirintda bo'sh kataklar ('.') va devorlar ('#') mavjud. Biz eng ko'pi bilan \(k\) ta devorni "buzib", oddiy bo'sh katakka aylantirgan holda \((1, 1)\) dan \((n, m)\) ga borish uchun ketadigan eng kam qadamlar sonini topishimiz kerak. Agar ilojsiz bo'lsa, \(-1\) chiqaramiz.

Asosiy g'oya (Shortest Path / BFS):

Bu turdagi eng qisqa yo'lni topish masalalarida BFS (Breadth-First Search - Eniga qidirish) algoritmidan foydalanamiz. Biroq, bu oddiy BFS emas, chunki bizda qo'shimcha resurs (\(k\) ta devor buzish imkoniyati) mavjud.

Holatni (state) quyidagicha belgilaymiz: \((r, c, \text{broken})\), bu yerda:

• \(r\) — hozirgi qator indeksi;
• \(c\) — hozirgi ustun indeksi;
• \(\text{broken}\) — shu paytgacha nechta devor buzib o'tilgani.

Cheklovlar kichik bo'lgani uchun (\(2 \le n, m \le 300\) va \(0 \le k \le \min(n \cdot m, 20)\)), holatlar soni unchalik katta emas.

Algoritm (0-1 BFS yoki Oddiy BFS + Visited massivi):

1. Navbat (Queue): BFS navbatiga boshlang'ich holatni qo'shamiz: \((1, 1, 0)\) — ya'ni \((1, 1)\) katakdamiz va hali \(0\) ta devor buzganmiz, qadamlar soni \(0\) ga teng.

2. Masofalar/Holatlar massivi (\(dist[r][c][broken]\)): Har bir katak uchun shu paytgacha sarflangan eng kam qadamlarni saqlab boramiz. Boshlang'ich qiymatlar cheksizlik (\(\infty\)) bilan to'ldiriladi.

3. Qadam tashlash:

• Hozirgi \((r, c)\) katakdan to'rtta qo'shni tomonga (yuqori, pastki, chap, o'ng) yuramiz.
• Agar qo'shni katak bo'sh ('.') bo'lsa, devor buzish soni o'zgarmaydi (\(\text{broken}\) o'zgarmaydi).
• Agar qo'shni katak devor ('#') bo'lsa, uni buzib o'tishimiz mumkin, bunda \(\text{broken} + 1\) ga teng bo'ladi (agar bu qiymat \(k\) dan oshib ketmasa).

4. Optimallashtirish: Har safar yangi holatga o'tganda qadamlar soni kamroq bo'lsagina uni navbatga qo'shamiz va dist massivini yangilaymiz.

5. \((n, m)\) katakiga yetib kelganimizdagi eng birinchi topilgan qadamlar soni eng qisqa yo'l bo'ladi (chunki BFS qadamma-qadam kengayib boradi). Agar oxirigacha borib bo'lmasa, \(-1\) chiqaramiz.

Murakkablik:

Vaqt murakkabligi: \(O(n \times m \times k)\) — har bir katak va har bir mumkin bo'lgan buzilgan devorlar soni holati uchun navbatdan bir marta o'tiladi. \(300 \times 300 \times 20 \approx 1.8 \times 10^6\) operatsiyani tashkil qiladi va vaqt chegarasiga bemalol ulguradi.
Xotira murakkabligi: \(O(n \times m \times k)\) — dist massivi va navbat uchun sarflanadigan xotira.