Chirigan apelsinlar
m × n o'lchamli grid berilgan. Har bir katak quyidagi qiymatlardan biriga ega:
0— bo'sh katak;1— yangi (sog'lom) apelsin;2— chirigan apelsin.
Har bir daqiqada, yangi apelsin — agar unga to'rtta tomondan (yuqori, pastki, chap, o'ng) birida chirigan apelsin ulashgan bo'lsa — u ham chiriydi.
Barcha yangi apelsinlar chiriguncha necha daqiqa o'tishini toping. Barcha yangi apelsinlar chiriy olmasa, -1 qaytaring.
Pastki-chap burchakdagi 1 hech qachon chirimaydigan yangi apelsin qoladi.
Yangi apelsin yo'q — 0 daqiqa.
Asosiy g'oya: multi-source BFS
Masala "barcha chirigan apelsinlardan bir vaqtda chirishni tarqatish" — bu multi-source BFS ning klassik namunasi.
BFS odatda bitta manbadan boshlanadi. Bu masalada esa bir nechta manba — barcha boshlang'ich chirigan apelsinlar — bir vaqtda faoldir. Ularning hammasi birinchi "qatlamni" tashkil qiladi. Har daqiqa — bir BFS qatlami.
Daqiqa 0:
2 1 1 Chirigan: (0,0)
1 1 0 Yangi: (0,1),(0,2),(1,0),(1,1),(2,1),(2,2)
0 1 1
Daqiqa 1:
2 2 1 (0,0) dan (0,1) va (1,0) chiridi
2 1 0
0 1 1
Daqiqa 2:
2 2 2 (0,1) dan (0,2); (1,0) dan (1,1) chiridi
2 2 0
0 1 1
Daqiqa 3:
2 2 2 (1,1) dan (2,1) chiridi
2 2 0
0 2 1
Daqiqa 4:
2 2 2 (2,1) dan (2,2) chiridi
2 2 0
0 2 2
Barcha yangi apelsinlar chirib bo'ldi. Javob: 4
Pseudocode
FUNCTION ORANGES_ROTTING(grid)
rows = grid qatorlar soni
cols = grid ustunlar soni
queue = bo'sh queue
fresh = 0 // yangi apelsinlar soni
// Boshlang'ich holatni tayyorlash
FOR row = 0 DAN rows - 1 GACHA
FOR col = 0 DAN cols - 1 GACHA
IF grid[row][col] = 2
queue.ENQUEUE((row, col, 0)) // (qator, ustun, daqiqa)
ELSE IF grid[row][col] = 1
fresh = fresh + 1
IF fresh = 0
RETURN 0 // yangi apelsin yo'q, 0 daqiqa
directions = [(0,1), (0,-1), (1,0), (-1,0)]
max_time = 0
WHILE queue bo'sh emas
(row, col, time) = queue.DEQUEUE()
FOR har bir (dr, dc) directions ichida
nr = row + dr
nc = col + dc
IF 0 ≤ nr < rows VA 0 ≤ nc < cols VA grid[nr][nc] = 1
grid[nr][nc] = 2 // chiridi
fresh = fresh - 1
max_time = MAX(max_time, time + 1)
queue.ENQUEUE((nr, nc, time + 1))
IF fresh > 0
RETURN -1 // ba'zi yangi apelsinlar chirimaganligi qoldi
RETURN max_time
Yoki time ni katakdan emas, qatlamni sanab boshqarish mumkin:
FUNCTION ORANGES_ROTTING_v2(grid)
rows = grid qatorlar soni
cols = grid ustunlar soni
queue = bo'sh queue
fresh = 0
FOR row = 0 DAN rows - 1 GACHA
FOR col = 0 DAN cols - 1 GACHA
IF grid[row][col] = 2
queue.ENQUEUE((row, col))
ELSE IF grid[row][col] = 1
fresh = fresh + 1
IF fresh = 0
RETURN 0
directions = [(0,1), (0,-1), (1,0), (-1,0)]
minutes = 0
WHILE queue bo'sh emas VA fresh > 0
level_size = queue hajmi
minutes = minutes + 1
FOR i = 0 DAN level_size - 1 GACHA
(row, col) = queue.DEQUEUE()
FOR har bir (dr, dc) directions ichida
nr = row + dr
nc = col + dc
IF 0 ≤ nr < rows VA 0 ≤ nc < cols VA grid[nr][nc] = 1
grid[nr][nc] = 2
fresh = fresh - 1
queue.ENQUEUE((nr, nc))
RETURN -1 IF fresh > 0 ELSE minutes
Bosqichma-bosqich dry run
Daqiqa 1 — level_size = 1:
(0,0) olinadi.
Qo'shnilar: (0,1) va (1,0) — ikkalasi '1'.
grid[0][1] = 2, fresh = 5, queue ga (0,1)
grid[1][0] = 2, fresh = 4, queue ga (1,0)
Holat:
2 2 1
2 1 0
0 1 1
queue = [(0,1), (1,0)]
Daqiqa 2 — level_size = 2:
(0,1) olinadi.
Qo'shnilar: (0,0)='2'→skip, (0,2)='1', (1,1)='1'
grid[0][2] = 2, fresh = 3, queue ga (0,2)
grid[1][1] = 2, fresh = 2, queue ga (1,1)
(1,0) olinadi.
Qo'shnilar: (0,0)='2'→skip, (2,0)='0'→skip, (1,1)='2'→skip
Yangi yo'q.
Holat:
2 2 2
2 2 0
0 1 1
queue = [(0,2), (1,1)]
Daqiqa 3 — level_size = 2:
(0,2) olinadi. Qo'shnilar: (1,2)='0'→skip, boshqalar '2'. Yangi yo'q.
(1,1) olinadi. Qo'shnilar: (2,1)='1'.
grid[2][1] = 2, fresh = 1, queue ga (2,1)
Holat:
2 2 2
2 2 0
0 2 1
queue = [(2,1)]
Daqiqa 4 — level_size = 1:
(2,1) olinadi. Qo'shnilar: (2,2)='1'.
grid[2][2] = 2, fresh = 0, queue ga (2,2)
Holat:
2 2 2
2 2 0
0 2 2
queue = [(2,2)]
Keyingi iteratsiya boshida fresh = 0 → WHILE sharti to'xtatadi.
Javob: 4
Vaqt va xotira murakkabligi
| Xususiyat | Qiymat | Izoh |
|---|---|---|
| Vaqt | O(m × n) |
Har katak bir marta ko'riladi |
| Xotira | O(m × n) |
Worst case: barcha kataklar queueda |
Har katak BFS davomida ko'pi bilan bir marta '1' dan '2' ga o'tkaziladi. Ikkinchi marta ko'rib chiqilmaydi.
Edge case'lar
Yangi apelsin yo'q. fresh = 0 — darhol 0 qaytariladi.
Chirigan apelsin yo'q, yangi bor. queue bo'sh boshlanadi, BFS hech ish qilmaydi, fresh > 0 bo'lib qoladi — -1 qaytariladi.
Yangi apelsin izolatsiyada. Suv bilan o'ralgan yoki bo'sh kataklar bilan ajralgan yangi apelsin hech qachon chirimaydigan holatda -1.
Barcha katak bo'sh. fresh = 0 — 0 qaytariladi.
Bitta katak grid. Agar chirigan bo'lsa — 0. Yangi bo'lsa — -1.
Warning
fresh sanagichsiz faqat BFS qatlamlarini sanash yetarli emas — izolatsiyalangan yangi apelsinni aniqlay olmaydi. fresh qolganini tekshirish -1 qaytarishni to'g'ri boshqaradi.
Keng tarqalgan xatolar
Bitta manbadan BFS boshlash. Multi-source BFS kerak — barcha boshlang'ich chirigan apelsinlar birinchi qatlamda bo'lishi shart. Bitta manbadan boshlanilsa, tarqalish vaqti noto'g'ri hisoblanadi.
Visited belgilashni kechiktirish. Yangi apelsin '2' ga o'zgartirish enqueue paytida bajarilishi kerak. Dequeue paytida bajarilsa, bir katak bir necha marta queuega tushib fresh noto'g'ri kamaytiriladi.
Bo'sh katak '0' ni tekshirmaslik. Bo'sh katak orqali apelsin chirishi kechishi mumkin emas — faqat grid[nr][nc] = 1 bo'lganda harakatlanish kerak.
Xulosa
Chirigan apelsinlar — multi-source BFS ning klassik masalasi. Barcha boshlang'ich chirigan apelsinlar birinchi qatlam sifatida bir vaqtda queuega solinadi. Har BFS qatlami — bir daqiqa. Eng chuqur qatlam — javob.
fresh sanagichi izolatsiyalangan yangi apelsinni aniqlash uchun muhim: BFS tugagach fresh > 0 bo'lsa, ba'zi apelsinlar hech qachon chirimaydigan holatda — -1.