Number of Islands

מפה מתקבלת כרשימה של שורות באורך שווה. כל תו הוא או 1, משבצת יבשה, או 0, משבצת מים. שתי משבצות יבשה שייכות לאותו אי כאשר אחת נמצאת ישירות מעל השנייה, מתחתיה, משמאלה או מימינה. משבצות שנוגעות זו בזו רק בפינה אינן מחוברות.

ניקח את המפה ["11000", "11000", "00100", "00011"]:

• ארבע משבצות היבשה בפינה השמאלית העליונה יוצרות אי אחד,
• המשבצת הבודדת בשורה האמצעית היא אי שני, משום שהיא נוגעת באי הראשון רק בפינה,
• שתי המשבצות בפינה הימנית התחתונה יוצרות אי שלישי.

לכן, יש במפה 3 איים.

המפה היא למעשה גרף: כל משבצת יבשה היא צומת, וקשת מחברת בין שתי משבצות יבשה שחולקות צלע. ספירת האיים פירושה ספירת החלקים המחוברים של הגרף. בכל פעם שמוצאים משבצת יבשה שעדיין לא ביקרת בה, מצאת אי חדש, וחוקרים את כולו לפני שממשיכים הלאה.

כתבו פונקציה בשם numIslands שמקבלת את grid, רשימה של מחרוזות המורכבות מ־1 (יבשה) ומ־0 (מים), ומחזירה את מספר האיים. אי הוא קבוצה של ריבועי יבשה המחוברים למעלה, למטה, משמאל או מימין.

לדוגמה, ["01110", "01000", "00011", "11001"] מחזירה 3: הצורה בשורות העליונות, הקבוצה מימין והזוג בפינה השמאלית התחתונה.

אילוצים: 1 <= מספר השורות, מספר העמודות <= 150. לכל השורות אותו אורך.