אתגר תכנותי: מספר איים

תיאור האתגר:

נתונה רשת המכילה תאים משני סוגים: 1 (יבשה) ו-0 (מים). עליך לספור את מספר האיים כאשר אי מוקף במים והוא נוצר על ידי חיבור גושי יבשה הסמוכים זה לזה באופן אופקי או אנכי אך לא באלכסון.

נראה כמה דוגמאות:

grid = [
    [0, 0],
    [0, 0],
]

• הרשת אינה מכילה איים היות והרשת כוללת אך ורק תאים המסומנים 0.

grid = [
    [0, 0],
    [0, 1],
]

• הרשת כוללת תא אחד המסומן 1, ועל כן אי 1.

grid = [
    [0, 1],
    [0, 1],
]

• הרשת מכילה תאים המסומנים 1 הנמצאים באותה עמודה אחד מתחת לשני, כאשר כל יתר התאים הם 0, ועל כן מכילה אי 1.

grid = [
    [0, 0],
    [1, 1],
]

• הרשת מכילה תאים המכילים 1 הנמצאים באותה שורה אחד לצד השני, כאשר כל יתר התאים הם 0, ועל כן מכילה אי אחד בודד.

grid = [
    [1, 0],
    [0, 1],
]

• ברשת זו שני איים היות והחיבור לאי אחד יכול להיות רק בין תאים סמוכים באותה שורה או עמודה אך לא באלכסון.

grid = [
    [1, 1, 0],
    [0, 0, 1],
]

• גם ברשת זו שני איים.

grid = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 1]
]

• ברשת זו 3 איים.

grid = [
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

• ברשת זו אי 1.

את הפתרון יש לכתוב בתוך הפונקציה:

def count_islands(grid: List[List[int]]) -> int:
    # Your code

פתרון 1

פתרון מבוסס אלגוריתם חיפוש לעומק DFS רקורסיבי:

def count_islands(grid) -> int:
   counter = 0


   if not grid or not grid[0]:
       return counter


   height, width = len(grid), len(grid[0])
   visited = set()
   steps = [(-1,0), (0,1), (1,0), (0,-1)]


   def traverse(y, x):
       visited.add((y, x))
       for dy, dx in steps:
           if 0 <= y+dy < height and 0 <= x+dx < width 
           and grid[y+dy][x+dx] == 1 
           and (y+dy, x+dx) not in visited:
               traverse(y+dy, x+dx)


   for y in range(height):
       for x in range(width):
           if grid[y][x] == 1 and (y, x) not in visited:
               traverse(y, x)
               counter += 1


   return counter

סיבוכיות הזמן והמקום הינה : O(M*N)

פתרון 2

פתרון מבוסס DFS איטרטיבי (לולאה ו- stack במקום רקורסיה):

from collections import deque


def count_islands(grid) -> int:
   counter = 0


   if not grid or not grid[0]:
       return counter


   height, width = len(grid), len(grid[0])
   visited = set()
   steps = [(-1,0), (0,1), (1,0), (0,-1)]


   def traverse(y, x):
       visited.add((y, x))
       stack = deque()
       stack.append((y, x))
       while stack:
           y, x = stack.pop()
           for dy, dx in steps:
               if 0 <= y+dy < height and 0 <= x+dx < width 
               and grid[y+dy][x+dx] == 1 
               and (y+dy, x+dx) not in visited:
                   visited.add((y+dy, x+dx))
                   stack.append((y+dy, x+dx))


   for y in range(height):
       for x in range(width):
           if grid[y][x] == 1 and (y, x) not in visited:
               traverse(y, x)
               counter += 1


   return counter

פתרון 3

אפשר לחסוך מקום בזיכרון אם במקום להשתמש בסט visited לשמירת הצמתים בהם ביקרנו, נשנה את סימון הקואורדינטה ב - grid בה ביקרנו מ-1 ל-2:

from collections import deque


def count_islands(grid) -> int:
   counter = 0
   height, width = len(grid), len(grid[0])
   steps = [(-1,0),(0,1),(1,0),(0,-1)]
   # debug = [[""]*width for _ in range(height)]


   def traverse(y, x):
       q = deque() # BFS, replace with stack = deque() for DFS
       q.append((y, x))
      
       # debug[y][x] = "x"
       while q:
           y, x = q.popleft() # BFS, replace with stack.pop() for DFS
           grid[y][x] = 2
           for dy, dx in steps:
               if 0 <= y+dy < height 
                   and 0 <= x+dx < width 
                       and int(grid[y+dy][x+dx]) == 1:
                               q.append((y+dy, x+dx))


   for y in range(height):
       for x in range(width):
           if int(grid[y][x]) == 1:
                   # debug[y][x] = "s"
                   traverse(y, x)
                   counter += 1
   # print(debug)
   return counter

פתרון 4

פתרון מבוסס אלגוריתם חיפוש לרוחב BFS :

from collections import deque


def count_islands(grid) -> int:
  counter = 0
  height, width = len(grid), len(grid[0])
  steps = [(-1,0),(0,1),(1,0),(0,-1)]
  # debug = [[""]*width for _ in range(height)]


  def traverse(y, x):
      q = deque() # BFS, replace with stack = deque() for DFS
      q.append((y, x))
    
      # debug[y][x] = "x"
      while q:
          y, x = q.popleft() # BFS, replace with stack.pop() for DFS
          grid[y][x] = 2
          for dy, dx in steps:
              if 0 <= y+dy < height 
                  and 0 <= x+dx < width 
                      and int(grid[y+dy][x+dx]) == 1:
                              q.append((y+dy, x+dx))


  for y in range(height):
      for x in range(width):
          if int(grid[y][x]) == 1:
                  # debug[y][x] = "s"
                  traverse(y, x)
                  counter += 1
  # print(debug)
  return counter

לבדיקת הפתרונות:

# Test cases
grid1 = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 1]
]

grid2 = [
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

grid3 = [
    [1, 0, 1],
    [0, 1, 1],
]

grid4 = [
    [0, 0],
    [0, 1],
]

grid5 = [
    [0, 0],
    [0, 0],
]

grid6 = [
    [1]
]

grid7 = [
    [0]
]

grid8 = []

test_cases = [
    [grid1, 3],
    [grid2, 1],
    [grid3, 2],
    [grid4, 1],
    [grid5, 0],
    [grid6, 1],
    [grid7, 0],
    [grid8, 0],
]

print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")
for grid, expected in test_cases:
    res = count_islands(grid)
    conclusion = "😄" if res == expected else "😭"
    print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")
print("Finito Programa")

מדריכים נוספים שעשויים לעניין אותך

אתגר תכנותי: שודד הבתים

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

אתגר תכנותי Decode ways - פענוח הדרכים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים