20-dars: Flood fill va panjara

3-darajaOltin — graflar17–24 darslar

HayotdaRasm

Rasm chizish programmasida «to’ldirish» asbobi bor: bitta joyni bosasiz va butun soha bo’yaladi. Programma qanday biladi qayerda to’xtashni? U qo’shni piksellarga tarqaladi va rangi boshqacha bo’lgan joyda to’xtaydi — hech qanday sehr yo’q.

Bu darsdan keyin siz

• panjarani graf sifatida ko’rasiz va qo’shnilarni koordinatadan hisoblaysiz
• flood fill bilan komponentalarni sanaysiz
• chekka tekshiruvlarini xatosiz yozasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·yakka·Katakli qog'oz va ikki rangli qalam

Katakli qog’ozda 8 × 8 maydon chizing va taxminan yarim kataklarni bo’yang — bular quruqlik, qolgani suv.

Endi orollarni sanang. Har yangi orolni boshqa rang bilan ustidan bo’yab chiqing: bitta katakdan boshlab, yonma-yon turgan hamma quruqlikka tarqaling.

Nimani sezishingiz kerak

Ikki narsa sezilgan bo’lishi kerak. Birinchisi: diagonal bo’yicha tegib turgan kataklar alohida orol — «yonma-yon» degan so’zni aniq belgilash kerak. Ikkinchisi: bo’yalgan katakka qayta kirilmadi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Panjara ham graf

flood fillflood fill

Bitta katakdan boshlab, unga bog’langan barcha kataklarni belgilab chiqish. Panjaradagi DFS yoki BFS ning boshqa nomi.

Farq bitta joyda: graf masalasida qo’shnilar ro’yxati saqlanadi, panjarada esa hisoblanadi. To’rt qo’shni koordinatadan chiqadi.

qoshnilarNusxalash

1YONALISH = ((-1, 0), (1, 0), (0, -1), (0, 1))2y, x = 2, 33for dy, dx in YONALISH:4  print(y + dy, x + dx)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1YONALISH = ((-1, 0), (1, 0), (0, -1), (0, 1))2y, x = 2, 33for dy, dx in YONALISH:4  print(y + dy, x + dx)

Sizning bashoratingizTekshirish

Javobni ko'rish

1 3
3 3
2 2
2 4

To'rt yo'nalish: yuqori, past, chap, o'ng. Diagonal kerak bo'lsa ro'yxatga yana to'rtta juftlik qo'shiladi — lekin shart buni aniq aytishi kerak.

▲Bu yerda xato qilishadi

Har qo’shni uchun ikki tekshiruv majburiy va tartibi muhim: avval panjara ichidami, keyingina katakning qiymati. Teskari yozilsa IndexError chiqadi — yoki, Python’da manfiy indeks tufayli, xato ham chiqmay noto’g’ri javob beradi.

Sekin yechim

Har quruqlik katagidan boshlab butun orolni qaytadan kezamiz va topilgan to’plamni saqlaymiz.

sekin.pyNusxalash

1xarita = ["##.", "#..", "..#"]2r, c = len(xarita), len(xarita[0])3orollar = set()4for i in range(r):5  for j in range(c):6      if xarita[i][j] != "#":7          continue8      korilgan = {(i, j)}9      stek = [(i, j)]10      while stek:11          y, x = stek.pop()12          for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):13              ny, nx = y + dy, x + dx14              if 0 <= ny < r and 0 <= nx < c and xarita[ny][nx] == "#":15                  if (ny, nx) not in korilgan:16                      korilgan.add((ny, nx))17                      stek.append((ny, nx))18      orollar.add(frozenset(korilgan))19print(len(orollar))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1xarita = ["##.", "#..", "..#"]2r, c = len(xarita), len(xarita[0])3orollar = set()4for i in range(r):5  for j in range(c):6      if xarita[i][j] != "#":7          continue8      korilgan = {(i, j)}9      stek = [(i, j)]10      while stek:11          y, x = stek.pop()12          for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):13              ny, nx = y + dy, x + dx14              if 0 <= ny < r and 0 <= nx < c and xarita[ny][nx] == "#":15                  if (ny, nx) not in korilgan:16                      korilgan.add((ny, nx))17                      stek.append((ny, nx))18      orollar.add(frozenset(korilgan))19print(len(orollar))

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Ikki orol: chap yuqoridagi uchta katak va o'ng pastdagi yolg'iz katak. Ular faqat diagonal bo'yicha tegib turibdi, demak alohida.

Nega sekin

Uch katakli orol uch marta, ming katakli orol ming marta qayta kezib chiqiladi. Xarita 500 × 500 bo’lishi mumkin — bu 250 ming katak.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 250 000
Har katakdan qayta kezishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Bir marta kezishn	1 000sig‘adi	250 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

korilgan butun xarita bo’ylab bitta marta yuritiladi. Yangi orol faqat hali bo’yalmagan quruqlik katagidan boshlanadi.

tez.pyNusxalash

1xarita = ["##..#", "#..#.", "..###", "#...#"]2r, c = len(xarita), len(xarita[0])3korilgan = [[False] * c for _ in range(r)]4orollar = 05for i in range(r):6  for j in range(c):7      if xarita[i][j] != "#" or korilgan[i][j]:8          continue9      orollar += 110      korilgan[i][j] = True11      stek = [(i, j)]12      while stek:13          y, x = stek.pop()14          for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):15              ny, nx = y + dy, x + dx16              if 0 <= ny < r and 0 <= nx < c:17                  if xarita[ny][nx] == "#" and not korilgan[ny][nx]:18                      korilgan[ny][nx] = True19                      stek.append((ny, nx))20print(orollar)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1xarita = ["##..#", "#..#.", "..###", "#...#"]2r, c = len(xarita), len(xarita[0])3korilgan = [[False] * c for _ in range(r)]4orollar = 05for i in range(r):6  for j in range(c):7      if xarita[i][j] != "#" or korilgan[i][j]:8          continue9      orollar += 110      korilgan[i][j] = True11      stek = [(i, j)]12      while stek:13          y, x = stek.pop()14          for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):15              ny, nx = y + dy, x + dx16              if 0 <= ny < r and 0 <= nx < c:17                  if xarita[ny][nx] == "#" and not korilgan[ny][nx]:18                      korilgan[ny][nx] = True19                      stek.append((ny, nx))20print(orollar)

Sizning bashoratingizTekshirish

Javobni ko'rish

4

To'rtta orol. Har katak aynan bir marta stekka tushadi, demak ish hajmi panjara o'lchamiga proporsional.

Sinab ko’r

Vizualda har yangi orol boshqa rangda bo’yaladi. Katak faqat bir marta ko’rilishini kuzating.

Flood fill — nechta orol

Har yangi orol boshqa rangda bo'yaladi. Katak faqat bir marta ko'riladi.

Har bo'yalmagan quruqlik katagidan boshlab butun bog'langan bo'lak to'lg'aziladi; necha marta boshlangan bo'lsa — shuncha orol.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. To'q kataklar — quruqlik. Yonma-yon turganlari bitta orol. Diagonal bo'yicha tegib turish yetarli emas.
2. Yangi orol topildi — 1-orol. (0, 0) katagidan to'lg'azishni boshlaymiz.
3. (0, 0) dan (1, 0), (0, 1) katagi shu orolga qo'shildi.
4. Yangi orol topildi — 2-orol. (0, 4) katagidan to'lg'azishni boshlaymiz.
5. Yangi orol topildi — 3-orol. (1, 3) katagidan to'lg'azishni boshlaymiz.
6. (1, 3) dan (2, 3) katagi shu orolga qo'shildi.
7. (2, 3) dan (2, 2), (2, 4) katagi shu orolga qo'shildi.
8. (2, 4) dan (3, 4) katagi shu orolga qo'shildi.
9. Yangi orol topildi — 4-orol. (3, 0) katagidan to'lg'azishni boshlaymiz.
10. Jami 4 ta orol. Har katak ANIQ BIR MARTA ko'rildi — 10 amal, panjara o'lchamiga proporsional.

0

1

2

3

To'q kataklar — quruqlik. Yonma-yon turganlari bitta orol. Diagonal bo'yicha tegib turish yetarli emas.

Bo'yalgan katak0

OrqagaO‘ynatishOldinga1/10Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

20 / 40

Masala500 x 500 panjarada orollar sonini toping.

Taklif qilingan yechim

1. 1Har katakni aylanib chiqamiz.
2. 2Bo‘yalmagan quruqlik topsak, orollar hisoblagichini oshiramiz.
3. 3O‘sha katakdan REKURSIV flood fill chaqiramiz va butun orolni belgilaymiz.
4. 4Sikl tugagach hisoblagichni chiqaramiz.

Bu javobning 3-qismi noto'g'ri. Rekursiv flood fill 500 x 500 panjarada RecursionError beradi: butunlay quruqlik bo'lgan xaritada chuqurlik 250 mingga yetadi, Python chegarasi esa ming atrofida. Mantiq to'g'ri, lekin yechim ishga tushmaydi. To'g'risi: rekursiya o'rniga stek yoki navbat.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Panjarada qo'shnilar qanday topiladi?

Javobni ko'rish

Koordinatadan hisoblanadi: (y-1, x), (y+1, x), (y, x-1), (y, x+1). Qo’shnilar ro’yxati saqlanmaydi.

2Nega avval chegara, keyin katak qiymati tekshiriladi?

Javobni ko'rish

Teskari tartibda xarita[ny][nx] panjaradan tashqarida chaqiriladi. Python manfiy indeksni oxiridan sanaydi, shuning uchun xato ham chiqmasligi va jimgina noto’g’ri javob berishi mumkin.

3Diagonal qo'shnilar hisobga olinadimi?

Javobni ko'rish

Faqat shart shuni aytsa. Sukut bo’yicha to’rt yo’nalish olinadi; sakkiz yo’nalish kerak bo’lsa ro’yxatga yana to’rtta juftlik qo’shiladi va javob butunlay o’zgarishi mumkin.

4Bu dars 18-dars bilan qanday bog'liq?

Javobni ko'rish

Bir xil masala: bog’langan guruhlarni sanash. Farqi faqat qo’shnilar saqlanadimi yoki hisoblanadimi degan joyda.

5Flood fill uchun stek va navbat orasida farq bormi?

Javobni ko'rish

Natijada yo’q — ikkalasi ham butun komponentani topadi. Farq faqat kezish tartibida. Eng qisqa masofa kerak bo’lsa navbat majburiy (19-dars).

Masalalar

Masalalar

3 ta

• Counting RoomsCSES 1192oson

  Darsdagi masalaning o‘zi. Rekursiyadan foydalanmang.

• Igor In the MuseumCodeforces 598Do'rta

  Har xona uchun javobni BIR MARTA hisoblang va xonadagi hamma katakka bir xil javobni bering.

• MazeCodeforces 377Aqiyin

  Teskari o‘ylang: devor qo‘yish o‘rniga, qolishi kerak bo‘lgan kataklarni kezib belgilang.

Lokal mashq: mashqlar/20-orollar/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Katakli qog’ozda 8 × 8 xarita chizing va orollarni qo’lda bo’yab sanang. Keyin diagonal ham qo’shni deb hisoblab qayta sanang — javob qanday o’zgardi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

20-orollar masalasini yeching. Chegara holatlarini sinang: butunlay suv, butunlay quruqlik, 1 × 1 xarita.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Masalani kengaytiring: eng katta orol nechta katakdan iborat va u qayerda boshlanadi? Keyin yana bir savol qo’shing — orollar ichida «ko’l» (quruqlik bilan o’ralgan suv) bormi va uni qanday aniqlaysiz?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim