岛周边 - 罚款时间限制 - python

Question

问题

您获得了行x col网格，代表一个地图，其中网格[i] [j] = 1代表土地，网格[i] [j] = 0代表水。

网格细胞水平/垂直连接（不是对角线）。网格完全被水包围，恰好有一个岛（即一个或多个连接的陆细胞）。

该岛没有“湖泊”，这意味着内部的水与岛上的水没有连接。一个单元格是一个具有侧长1的正方形。网格是矩形，宽度和高度不超过100。确定岛的周长。

示例1：

输入：grid = [[0,1,0,0]，[1,1,1,0]，[0,1,0,0]，[1,1,0,0]] 输出：16 说明：周长是上图中的16个黄色条纹。

​代码：

IslandPerimeter（）是解决方案函数

def islandPerimeter(self, grid: List[List[int]]) -> int:
    v=[[0,0]]
    q=[[0,0]]
    c=0
    return self.bfs(grid,v,q,c)

def bfs(self,grid,v,q,c):
    if q==[]:
        return c
    i=q[0][0]
    j=q[0][1]
    if grid[i][j]:
        c+=4
    if i-1 > -1:
        if [i-1,j] not in v:
            q.append([i-1,j])
            v.append([i-1,j])
        if grid[i-1][j] and grid[i][j]:
            c-=1
    if j-1 > -1:
        if [i,j-1] not in v:
            q.append([i,j-1])
            v.append([i,j-1])
        if grid[i][j-1] and grid[i][j]:
            c-=1
    try:
        a=grid[i+1][j]
        if [i+1,j] not in v:
            q.append([i+1,j])
            v.append([i+1,j])
        if grid[i+1][j] and grid[i][j]:
            c-=1
    except:
        pass
    try:
        a=grid[i][j+1]
        if [i,j+1] not in v:
            q.append([i,j+1])
            v.append([i,j+1])
        if grid[i][j+1] and grid[i][j]:
            c-=1
    except:
        pass
    del q[0]


    return self.bfs(grid,v,q,c)

q = bfs

v =访问阵列

i =行j =列

j =列

C =最终答案

我从（0,0）单元格开始，并使用BFS穿越了图。对于每个岛屿细胞，我将计数增加了4，对于每个岛屿细胞，如果相邻的细胞是一个岛屿细胞，那么对于每个这样的岛屿细胞，我都将计数减少1。 但是我得到的时间限制超过了错误。

Answer 1

恰好有一个岛

==＆gt;

每个陆区都连接到每个Opther Land Tell，

因此您可以简化算法

• 搜索单元格，以便订购，例如，左上列列列行，行沿行右下 - 右下 - 在第一次找到陆区时停止。
• 搜索邻居在水牢房时追踪陆细胞的回程 - 记录所有发现的陆细胞