Python程序：查找岛屿形状的周长

假设我们有一个二进制矩阵，其中 0 表示空单元格，1 表示形成形状的块，现在我们必须找到形状的周长。该形状内部不会包含任何孔。

因此，如果输入类似于

则输出将为 14。

为了解决这个问题，我们将遵循以下步骤：

• d := 0

• perimeter := 0

• height := 矩阵的行数

• length := 矩阵的列数

• 对于矩阵中的每一行，执行以下操作：

  • c := 0

  • 对于行中的每个值，执行以下操作：

    • 如果值与 1 相同，则

      • surround := 4

      • 如果 c 与 length - 1 不相同，则

        • 如果 matrix[d, c + 1] 与 1 相同，则

          • surround := surround - 1

      • 如果 c 与 0 不相同，则

        • 如果 matrix[d, c - 1] 与 1 相同，则

          • surround := surround - 1

      • 如果 d 与 height - 1 不相同，则

        • 如果 matrix[d + 1, c] 与 1 相同，则

          • surround := surround - 1

      • 如果 d 与 0 不相同，则

        • 如果 matrix[d - 1, c] 与 1 相同，则

          • surround := surround - 1

      • perimeter := perimeter + surround

      • c := c + 1

  • d := d + 1

• 返回 perimeter

让我们查看以下实现以更好地理解：

示例

 在线演示

class Solution:
   def solve(self, matrix):
      d = 0
      perimeter = 0
      height = len(matrix)
      length = len(matrix[0])
      for line in matrix:
         c = 0

         for val in line:
            if val == 1:
               surround = 4
               if c != length - 1:
                  if matrix[d][c + 1] == 1:
                     surround -= 1
               if c != 0:
                  if matrix[d][c - 1] == 1:
                     surround -= 1
               if d != height - 1:
                  if matrix[d + 1][c] == 1:
                     surround -= 1
               if d != 0:
                  if matrix[d - 1][c] == 1:
                     surround -= 1
               perimeter += surround
            c += 1
         d += 1
      return perimeter

ob = Solution()
matrix = [
   [0,0,0,0,0],
   [0,0,1,1,1],
   [0,0,1,1,0],
   [0,1,1,1,0],
   [0,0,0,0,0]
]
print(ob.solve(matrix))

输入

matrix = [
[0,0,0,0,0],
[0,0,1,1,1],
[0,0,1,1,0],
[0,1,1,1,0],
[0,0,0,0,0]]

输出

14

Arnab Chakraborty

更新于: 2020年10月9日

385 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始