Number of Islands
تحصل على خريطة على شكل قائمة من السلاسل النصية المتساوية في الطول، حيث يمثّل '1' مربعًا من اليابسة ويمثّل '0' مربعًا من الماء. ينتمي مربعا يابسة إلى الجزيرة نفسها عندما يتشاركان ضلعًا: من الأعلى أو الأسفل أو اليسار أو اليمين. المربعات التي لا تلتقي إلا عند زاوية غير متصلة. أعد عدد الجزر.
الدالة
- gridstring-array
- الخريطة، سلسلة واحدة لكل صف
- تُرجعinteger
- عدد الجزر
القيود
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- كل صف له الطول نفسه.
- كل محرف هو
'0'أو'1'.
أمثلة
- المدخلات
- grid = ["11000", "11000", "00100", "00011"]
- المخرجات
- 3
- الشرح
- المربعات الأربعة في أعلى اليسار تشكّل جزيرة واحدة. المربع الأوسط في الصف الثالث يلامسها عند زاوية فقط، لذا فهو جزيرة ثانية. والزوج في أسفل اليمين هو الجزيرة الثالثة.
- المدخلات
- grid = ["01110", "01000", "00011", "11001"]
- المخرجات
- 3
- الشرح
- المربعات الثلاثة في الصف العلوي والمربع الواقع أسفل طرفه الأيسر تُشكّل جزيرة واحدة. والزوج الموجود في الجهة اليمنى من الصف الثالث يتصل نزولًا بالمربع السفلي الأيمن، ليشكّل جزيرة ثانية. والزوج السفلي الأيسر هو الجزيرة الثالثة.
سؤال إضافي
تظهر اليابسة الآن مربعًا واحدًا في كل مرة على خريطة مائية. هل يمكنك الإبلاغ عن عدد الجزر بعد كل مربع جديد دون مسح الخريطة بأكملها مرة أخرى؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
امسح الخريطة مربعًا مربعًا. عندما تصل إلى مربع أرض لم تطالب به أي جزيرة سابقة، فكم جزيرة جديدة اكتشفت؟
بمجرد أن تعثر على جزيرة جديدة، زُر كل مربع أرض متصل بها وحدد كلًّا منها على أنه تمت رؤيته، حتى لا يحتسب الفحص الجزيرة نفسها مرة أخرى.
استكشف باستخدام طابور (بحث بالعرض أولًا) أو مكدس صريح (بحث بالعمق أولًا) من المربعات التي لا تزال بحاجة إلى الزيارة. قد ينفد مكدس الاستدعاءات في البحث递ي على خريطة تتكون من جزيرة واحدة هائلة، بينما لا يحدث ذلك عند استخدام حلقة على الطابور أو المكدس الخاص بك.
الحل
اعتبر كل مربع من اليابسة عقدة متصلة بمربعات اليابسة المجاورة له: فالجزيرة جزء واحد متصل. امسح الخريطة، وكلما وصلت إلى يابسة لم ترها من قبل، احتسب جزيرة جديدة واملأها بطريقة الانتشار، مع وضع علامة على كل مربع فيها كي لا يحتسبها المسح مرة أخرى.
ملء المنطقة باستخدام مكدّس صريح (البحث بالعمق أولًا)
الفكرة
لا يمكن أن تنتمي مربّع أرض غير معلَّم إلى جزيرة سبق أن أحصيتها، لأن إحصاء الجزيرة يعلّمها بالكامل. لذا فهو يبدأ جزيرة جديدة. وتعلّم بقية الجزيرة باستخدام مكدّس تديره بنفسك: كل مربّع تخرجه من المكدّس يضيف جيرانه غير المعلَّمين من اليابسة، وعندما يصبح المكدّس فارغًا تكون الجزيرة كلها قد عُلِّمت.
مكدّسك الخاص مهم لأن التعبئة التكرارية قد تصل إلى عمق 22,500 استدعاء على خريطة 150 × 150 من اليابسة المتصلة. يُضاف كل مربّع إلى المكدّس مرة واحدة كحد أقصى، ويُفحَص جيرانه الأربعة، لذا فالزمن هو O(rows × cols). وتستهلك العلامات والمكدّس مساحة O(rows × cols) عندما تكون الخريطة كلها يابسة.
الخوارزمية
- أنشئ علامة «تمت زيارته» لكل خلية واضبط العدد على 0.
- افحص كل خلية، مع تخطي الماء والخلايا التي تمت زيارتها بالفعل.
- في اليابسة التي لم تتم زيارتها، أضف 1 إلى العدد، وضع علامة على الخلية وادفعها إلى مكدس.
- ما دام المكدس غير فارغ، أخرج خلية وادفع إليه كل جار داخل الخريطة لم تتم زيارته وكان يابسة، مع وضع علامة عليه قبل دفعه.
- أعِد العدد عند انتهاء الفحص.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countتعبئة المنطقة باستخدام طابور (BFS)
الفكرة
يعمل العد بالطريقة نفسها؛ الذي يتغير فقط هو ترتيب الزيارة. يأخذ الطابور المربعات من المقدمة ويضيف جيران اليابسة غير المحددين إلى الخلف، لذا يزور الجزيرة على شكل حلقات: المربع الأول، ثم كل مربع يبعد خطوة واحدة، ثم المربعات التي تبعد خطوتين. تظل زيارة كل مربع مرة واحدة، في زمن ومساحة O(rows × cols).
يحدد ترتيب الحلقات بُعد كل مربع عن نقطة البداية، لذا تجيب الحلقة نفسها عن أسئلة أقصر مسار على شبكة، مع رقم إضافي واحد لكل مربع.
الخوارزمية
- أنشئ علامة «تمت رؤيته» لكل مربع، واجعل العدد 0.
- امسح كل مربع، مع تخطي الماء والمربعات التي تمت رؤيتها بالفعل.
- عند الوصول إلى أرض غير مرئية، أضف 1 إلى العدد، وضع علامة على المربع وأضفه إلى قائمة انتظار فارغة.
- ما دامت قائمة الانتظار تحتوي على مربعات، خذ مربعًا من مقدمتها وأضف إلى نهايتها كل جار داخل الخريطة يمثل أرضًا غير مرئية، مع وضع علامة عليه عند إضافته.
- أعِد العدد عند انتهاء المسح.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
أخطاء شائعة وحالات حدّية
- وضع علامة على المربّع عند إخراجه من المكدّس أو الطابور بدلًا من وضعها عند إدخاله. وبذلك يدخل المربّع نفسه عدة مرات.
- مقارنة المربّع بالرقم 1 بدلًا من الحرف
'1'. كل صف عبارة عن سلسلة نصية، لذا فإن كل مربّع هو حرف. - قراءة أحد المربّعات المجاورة قبل التحقق من
0 ≤ row < rowsو0 ≤ col < cols. عندها تؤدي قراءة مربّع أرض على الحافة إلى الخروج عن الخريطة. - كتابة عملية الملء بشكل递归. تتوقف Python افتراضيًا عند 1,000 استدعاء، وقد تتجاوز لغات أخرى سعة المكدّس عند معالجة جزيرة كبيرة واحدة.
- أخذ العنصر الأول من قائمة Python باستخدام
pop(0)، إذ يستغرق ذلك وقتًا يتناسب مع طول القائمة. استخدمcollections.dequeوpopleft().
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة عدد الجزر؟
O(rows × cols). يفحص المسح كل مربع مرة واحدة، وتُضاف كل خانة من اليابسة إلى المكدس أو الطابور مرة واحدة، وتُفحص جيرانها الأربعة. تستخدم علامات الزيارة والمكدس أو الطابور مساحة O(rows × cols) على خريطة كلها يابسة.
هل ينبغي أن تستخدم BFS أم DFS لمسألة عدد الجزر؟
كلاهما صحيح في الوقت والمساحة نفسيهما، لأن العدّ يتطلب فقط وضع علامة على كل مربع في الجزيرة. لا تستخدم خوارزمية البحث بعرض الشجرة (BFS) مع قائمة انتظار الاستدعاء الذاتي مطلقًا؛ ويكون البحث بعمق الشجرة (DFS) آمنًا بالقدر نفسه عند استخدام مكدس صريح.
هل يمكنك حل مسألة عدد الجزر باستخدام بنية الاتحاد-البحث؟
نعم. ضع كل خلية أرض في مجموعة خاصة بها، وابدأ العدّ بعدد خلايا الأرض. ادمج كل زوج من خلايا الأرض المتجاورة، وأنقص العدّ بمقدار واحد كلما أدى الدمج إلى وصل مجموعتين مختلفتين. مع ضغط المسارات، يقترب الزمن من O(rows × cols).
هل يمكنك عدّ الجزر دون مصفوفة منفصلة للعناصر التي تمت زيارتها؟
نعم، إذا كان بإمكانك تغيير الخريطة: حوّل كل مربع من اليابسة إلى ماء بمجرد وصولك إليه. لا تستطيع لغات كثيرة تغيير السلاسل النصية في مكانها، لذا انسخ الصفوف أولًا إلى شبكة من الأحرف، وهذا يستهلك المساحة نفسها التي تستهلكها علامات المواقع التي تمت زيارتها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def numIslands(grid):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
grid = ["11000", "11000", "00100", "00011"]
الإخراج المتوقع
3