计算与 0 共享的矩阵中 1 的边数

Question

我们有一个包含 0 和 1 的矩阵。

类似于岛数问题

我需要找出 1 与 0 和外部世界（即矩阵的边界）共享的总边（左、右、上、下）。

示例：

所以，14 + 4 + 4 = 22

第一组 14 个

4 来自其他 2 个组

我们需要找出岛与0或矩阵边界接触的长度。在示例中，有 3 个岛，其中两个是单个 1。因此它们接触 0 和矩阵边界，所有四个边（上、下、右和左）。第三个岛由 6 个 1 组成，并将 1 与 0 共有的 4 个边中的所有 1 边相加，矩阵边界为 14。

这是我的代码。

class graphe:
def __init__(self,row,col,g):
    self.row=row
    self.col=col
    self.graph=g

def valid(self,i,j):
    return (i>=0 and i < self.row and j>=0 and j< self.col )


def dfs(self,t):
    r = [0,0,1,-1]
    c = [1,-1,0,0]
    total = 0
    for ii in t:
        i = ii[0]
        j = ii[1]
        for k in range(4):
            if self.valid(i+r[k],j+c[k]):
                if self.graph[i+r[k]][j+c[k]] == 0:
                    total += 1
            else:
                total += 1
    return total


for _ in range(int(input())):
    n,m,k = map(int,input().split())
    graph = [ [0 for i in range(m)] for j in range(n)]
    t = []
    for i in range(k):
        a,b = map(int,input().split())
        graph[a-1][b-1] = 1
        t.append([a-1,b-1])

    g = graphe(n,m,graph)

    print(g.dfs(t))

Answer 1

您需要计算矩阵中每一行和每一列从 0 到 1 和 1 到 0 的变化。

矩阵的边缘可以算作零。对于第 0 行，我们有 0 => 1=> 0 => 1 => 0 的变化。4 处变化。

对于第 2 列，我们有 0 => 1 => 0 的变化。2 处变化。

一起计算所有变化（叉号），您就完成了。

计算与 0 共享的矩阵中 1 的边数

Count sides of 1's in matrix which it shares with 0

algorithm

graph

matrix

depth-first-search