У нас есть матрица, которая содержит 0 и 1.
По аналогии с проблемой числа островов.
Мне нужно выяснить общее количество сторон (влево, вправо, вверх, вниз), которые1 делится с 0 и с внешним миром (то есть границей матрицы).
Пример:
1 0 1 0 0
1 1 1 0 1
0 1 0 0 0
1 0 0 0 0
Итак, 14 + 4 + 4 = 22 * 1010 *
14из первой группы
4 из других 2 групп
Нам нужно выяснить длину касания острова с 0 или границей матрицы.В примере есть 3 острова и два из них одиночные 1. Таким образом, они касаются 0 и границы матрицы со всеми четырьмя сторонами (вверх, вниз, вправо и влево).И 3-й остров состоит из 6 единиц 1 и добавления всех сторон 1 из 4 сторон, доля которых, общая с 0, и граница матрицы равны 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))