leetcode with python:463. Island Perimeter

题目:

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j]= 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

给定一二维阵列作为一座岛的地图,1表陆地,0表水
回传该岛的周长

我遍历整个二维阵列来计算周长

class Solution:    def islandPerimeter(self, grid: List[List[int]]) -> int:        row=len(grid)        column=len(grid[0])        ans=0                for i,m in enumerate(grid):            for j,n in enumerate(m):                if n==0:                    continue                                    plus=4                                if i>0 and grid[i-1][j]==1:                    plus=plus-1                if i<row-1 and grid[i+1][j]==1:                    plus=plus-1                if j>0 and grid[i][j-1]==1:                    plus=plus-1                if j<column-1 and grid[i][j+1]==1:                    plus=plus-1                                    ans=ans+plus                          return ans

一块陆地最多可以提供长度四的周长,但那也要它四面环水
若一边连接陆地其提供的周长便会少1

于是我开始遍历所有阵列元素
水不提供周长,直接略过
陆地先假设它会提供4的周长(plus)
而其四面每有一面是陆地就将plus-1
最后加到ans上,完全遍历完后回传ans
最后执行时间517ms(faster than 94.13%)

在讨论区,我有看到递迴的做法如下

class Solution:    def islandPerimeter(self, grid: List[List[int]]) -> int:        visit=set()                def dfs(i,j):            if i>=len(grid) or j>=len(grid[0]) or i<0 or j<0 or grid[i][j]==0:                return 1            if (i,j) in visit:                return 0                        visit.add((i,j))                        return dfs(i,j+1)+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j-1)                 for i in range(len(grid)):            for j in range(len(grid[0])):                if grid[i][j]==1:                    return dfs(i,j)

由于题目确定岛只有一座
所以我们可以藉由一块陆地扩张找出岛的周长

以一块陆地为起始,往上下左右扩张
纪录每个走过的土地
若为没走过的陆地则继续上下左右扩张
若为走过的陆地不继续扩张,回传0
若为水或地图边界则表示我们找到了岛的边界,回传1
找到的边界总和即为岛的周长
最后执行时间645ms(faster than 80.11%)

那我们下题见