广搜时记录答案?
from collections import deque
class Solution:
def islandPerimeter(self, grid) -> int:
n, m = len(grid), len(grid[0])
vis = [[0] * m for i in range(n)]
def check(x, y):
if 0 <= x < n and 0 <= y < m and vis[x][y] == 0 and grid[x][y] == 1:
return True
return False
def BFS(sx, sy):
q = deque([(sx, sy)])
vis[sx][sy] = 1
cnt = 0
while q:
x, y = q.popleft()
for tx, ty in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if check(tx, ty) == True:
vis[tx][ty] = 1
q.append((tx, ty))
elif tx < 0 or tx >= n or ty < 0 or ty >= m or grid[tx][
ty] == 0:
cnt += 1
return cnt
ans = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and vis[i][j] == 0:
ans += BFS(i, j)
return ans
