Orollar soni

m × n o'lchamli ikki o'lchamli grid (matritsa) berilgan. Har bir katak '1' (quruqlik) yoki '0' (suv) qiymatiga ega. Bir-biriga gorizontal yoki vertikal yo'nalishda ulangan quruqlik kataklar to'plami orol deyiladi. Orollar sonini toping.

Kirish:
  1 1 1 1 0
  1 1 0 1 0
  1 1 0 0 0
  0 0 0 0 0

Chiqish: 1

Bu gridda barcha '1' kataklar bir-biriga ulangan — bitta orol.

Kirish:
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

Chiqish: 3

Bu gridda uchta alohida guruh — uchta orol.

Asosiy g'oya: grid — implicit graf

Bu masala aslida grafda connected componentlarni sanash masalasi.

Har bir '1' katak vertex, unga ulangan boshqa '1' kataklarga yo'l esa edge. Ikki katak bir-biriga gorizontal yoki vertikal yo'nalishda ulangan bo'lsa, ular bir orolga tegishli — ya'ni bir componentda.

Maqsad: grafning nechta connected componenti borligini topish.

Yondashuv: 1. Grid bo'ylab yurib har uchraydigan '1' katakni ko'rish. 2. Bunday katak yangi orolning bir qismi — undan DFS yoki BFS boshlab, shu orolga tegishli barcha kataklar visited deb belgilanadi. 3. Har yangi boshlanish orollar sonini bir oshiradi. 4. Allaqachon ko'rilgan katak uchrasa — u hozirgi yoki oldingi orolga tegishli. O'tkazib yuboriladi.

Pseudocode

FUNCTION NUM_ISLANDS(grid)
    IF grid bo'sh bo'lsa
        RETURN 0

    rows  = grid qatorlar soni
    cols  = grid ustunlar soni
    count = 0

    FOR row = 0 DAN rows - 1 GACHA
        FOR col = 0 DAN cols - 1 GACHA
            IF grid[row][col] = '1'
                count = count + 1
                DFS(grid, row, col)

    RETURN count

FUNCTION DFS(grid, row, col)
    IF row < 0 YO row >= rows        RETURN
    IF col < 0 YO col >= cols        RETURN
    IF grid[row][col] ≠ '1'          RETURN

    grid[row][col] = '0'   // visited sifatida belgilash: asl qiymatni o'zgartirish

    DFS(grid, row + 1, col)
    DFS(grid, row - 1, col)
    DFS(grid, row, col + 1)
    DFS(grid, row, col - 1)

visited uchun alohida to'plam o'rniga grid qiymatini '0' ga o'zgartirish ishlatiladi. Bu xotirani tejaydi. Asl gridni o'zgartirish mumkin bo'lmasa, alohida visited boolean matritsa kerak.

Bosqichma-bosqich dry run

Boshlang'ich holat:
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

(0,0) — '1' topildi. count = 1. DFS boshlanadi:

DFS(0,0): grid[0][0]='0'
  DFS(1,0): grid[1][0]='0'
    DFS(2,0): grid[2][0]='0' emas → RETURN
    DFS(0,0): '0' → RETURN
    DFS(1,1): grid[1][1]='0'
      DFS(2,1): '0' → RETURN
      DFS(0,1): grid[0][1]='0'
        DFS(-1,1): chegaradan tashqari → RETURN
        DFS(1,1): '0' → RETURN
        DFS(0,2): '0' → RETURN
        DFS(0,0): '0' → RETURN
      DFS(1,2): '0' → RETURN
      DFS(1,0): '0' → RETURN
    DFS(1,-1): chegaradan tashqari → RETURN
  ...

DFS tugagach grid:

Yuqori-chap blokdagi barcha '1' lar '0' ga aylandi.

(2,2) — '1' topildi. count = 2. DFS boshlanadi:

(2,2) o'zi va unga ulanganlar '0' ga aylanadi.

(3,3) — '1' topildi. count = 3. DFS boshlanadi:

(3,3) va (3,4) '0' ga aylanadi.

Javob: 3

BFS bilan yechim

DFS o'rniga BFS ham ishlatish mumkin:

FUNCTION DFS_NI_BFS_BILAN(grid, start_row, start_col)
    queue = [(start_row, start_col)]
    grid[start_row][start_col] = '0'

    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    WHILE queue bo'sh emas
        (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] = '0'
                queue.ENQUEUE((nr, nc))

BFS va DFS bir xil natija beradi. DFS kodda soddaroq; BFS juda katta orolda rekursiya chuqurligi cheklov bo'lsa muqobil.

Vaqt va xotira murakkabligi

Xususiyat	Qiymat	Izoh
Vaqt	`O(m × n)`	Har katak bir marta ko'riladi
Xotira (DFS)	`O(m × n)`	Worst case: barcha katak `'1'`, rekursiya chuqurligi
Xotira (BFS)	`O(min(m, n))`	Worst case: eng keng diagonal

Vaqt murakkabligi O(m × n): tashqi tsikl har katakni bir marta ko'radi, DFS faqat '1' bo'lgan kataklar uchun ishga tushadi va ular '0' ga aylantiriladi — ikkinchi marta ko'rilmaydi.

Edge case'lar

Bo'sh grid. m = 0 yoki n = 0 — RETURN 0.

Hammasi suv. Hech qanday '1' katak yo'q — count = 0.

Hammasi quruqlik. Barcha kataklar '1' — bitta ulkan orol, count = 1.

Bitta qator yoki ustun. Yo'nalish vektori chegarani tekshirganligi sababli muammo yo'q.

Diagonal ulanish. Bu masalada diagonallar hisoblanmaydi. Faqat gorizontal va vertikal 4 yo'nalish — shuning uchun direction vektori 4 ta.

Note

Agar 8 yo'nalishli ulanish (diagonal ham) talab qilinsa, direction vektori 8 ta bo'ladi va shu bilan orollar soni o'zgarishi mumkin.

Keng tarqalgan xatolar

Visited ni belgilashni kechiktirish. BFSda '0' ga o'zgartirish enqueue paytida emas dequeue paytida qilinsa, bir katak bir necha marta queuega tushadi. Enqueue paytida belgilash kerak.

Chegarani tekshirmaslik. DFS da har rekursiv chaqiruvdan oldin row va col grid chegarasida ekanligini tekshirish shart — aks holda out-of-bounds xatosi.

Diagonal yo'nalishlarni qo'shish. Masala faqat 4 yo'nalishni talab qiladi. 8 yo'nalish qo'shilsa orollar soni kamayadi — ko'proq katak ulanadi.

Xulosa

Orollar soni — grid asosidagi connected component sanash masalasi. Har yangi ko'rilmagan '1' katakdan DFS yoki BFS ishga tushirib, shu orolga tegishli barcha kataklar visited belgilanadi. Har ishga tushish orollar sonini bir oshiradi.

Yechim O(m × n) vaqt oladi — har katak bir marta ko'riladi. Grid qiymatini o'zgartirish orqali alohida visited to'plami ishlatmaslik xotirani tejaydi.