ค้นหาจำนวนเกาะที่แตกต่างกันในเมทริกซ์ 2 มิติใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องนับจำนวนเกาะในนั้น เกาะเป็นสถานที่ที่ล้อมรอบด้วยน้ำและเกิดขึ้นจากการเชื่อมต่อดินแดนที่อยู่ติดกันในแนวนอนหรือแนวตั้ง เราสามารถสรุปได้ว่าขอบทั้งสี่ของตารางถูกล้อมรอบด้วยน้ำทั้งหมด

สมมติว่ากริดเป็นเหมือน −

มีสามเกาะ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จะมีสองวิธี วิธีหนึ่งจะใช้เพื่อนับจำนวนเกาะที่เรียกว่า numIslands() และ makeWater() makeWater() จะเป็นแบบ −

• ถ้าจำนวนแถวในตารางเป็น 0 ให้คืนค่า 0

• n =จำนวนแถว และ m :=จำนวนคอลัมน์ และ :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • สำหรับ j ในช่วง 0 ถึง m

    • ถ้า grid[i, j] =1 แล้ว ans :=ans + 1

    • makeWater(i, j, n, m, กริด)

• makeWater() จะนำดัชนี i, j, row และ col นับ n และ m และกริด

• ถ้า i <0 หรือ j <0 หรือ i>=n หรือ j>=m ให้กลับมาจากวิธีนี้

• ถ้า grid[i, j] =0 ให้คืนค่าเป็นอย่างอื่น make grid[i, j] :=0

• โทร makeWater(i + 1, j, n, m, grid)

• โทร makeWater(i, j + 1, n, m, grid)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

คลาส Solution(object):def numIslands(self, grid):""" :type grid:List[List[str]] :rtype:int """ if len(grid) ==0:return 0 n =len(grid) m =len(grid[0]) ans =0 สำหรับฉัน ในช่วง (n):สำหรับ j ในช่วง (m):if grid[i][j] =="1":ans+=1 self.make_water(i,j,n,m,grid) return และ def make_water(self,i,j,n,m,grid):ถ้า i<0 หรือ j<0 หรือ i>=n หรือ j>=m :return if grid[i][j] =="0":return else:grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water( i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,กริด)

อินพุต

ผลลัพธ์

3