class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
return 0
grid[i][j] = -1
ans = 4 + dfs(i + 1, j) + dfs(i - 1, j) + \
dfs(i, j + 1) + dfs(i, j - 1)
if i > 0 and grid[i - 1][j] != 0:
ans -= 2
if j > 0 and grid[i][j - 1] != 0:
ans -= 2
return ans
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
return dfs(i, j)
当然, 你选择判断右侧和下方也是一样的,只需要改两行代码即可,这两种算法没有什么区别。代码:
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
return 0
grid[i][j] = -1
ans = 4 + dfs(i + 1, j) + dfs(i - 1, j) + \
dfs(i, j + 1) + dfs(i, j - 1)
# 这里需要变
if i < m - 1 and grid[i + 1][j] != 0:
ans -= 2
# 这里需要变
if j < n - 1 and grid[i][j + 1] != 0:
ans -= 2
return ans
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
return dfs(i, j)