Наткнулся на такую задачу:
Удаление клеток:
Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Входные данные
В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.
Выходные данные
Вывести одно число.
Примеры
входные данные
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
выходные данные
5
Мое решение на Python:
1. Пусть все символы '#' соответствуют вершинам, пронумерованным от 1 до num_vertex (число всех вершин).
Создадим массив массивов R, в котором будет хранить номера вершин и заведем счетчик, чтобы посчитать количество вершин. Если R[i][j] = 0, то элемент, лежащий на i-й строке в j-й позиции является точкой (не вершиной), а иначе это вершина с номером R[i][j].
2. Создадим матрицу смежности vertex_num на vertex_num matrix, где matrix[i][j] = 0, если вершина i не смежна с вершиной j и 1, если смежна. Создадим ее таким образом: будем просматривать элементы в R и, в определенных случаях [когда невырезанная клетка граничит с другими невырезанными(например, на строке выше или ниже при той же позиции в строке, или в данной строке, но на позиции слева или справа)], будем отмечать в matrix смежные вершины. Например, для примера на входе матрица смежности будет выглядеть так:
matrix = [[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]]
В каждом списке матрицы по 27 элементов, поскольку всего символов '#' 27.
3. Создадим массив visited посещенных элементов. Далее будем запускать DFS от первого непосещенного элемента, пока все элементы не будут посещены, каждый раз увеличивая кол-во компонент связности на 1.
Код:
m,n = map(int,input().split())
R = [[] for i in range(m)]
num_vertex = 0
for i in range(m):
A = input()
for j in range(n):
if A[j] == '#':
num_vertex += 1
R[i].append(num_vertex)
else:
R[i].append(0)
matrix = [[0]*num_vertex for i in range(num_vertex)]
for i in range(m):
for j in range(n):
if R[i][j] != 0:
if j-1 >= 0 and R[i][j-1] != 0:
matrix[R[i][j-1]-1][R[i][j]-1],matrix[R[i][j]-1][R[i][j-1]-1] = 1,1
if j+1 <= n-1 and R[i][j+1] != 0:
matrix[R[i][j+1]-1][R[i][j]-1],matrix[R[i][j]-1][R[i][j+1]-1] = 1,1
if i-1 >= 0 and R[i-1][j] != 0:
matrix[R[i-1][j]-1][R[i][j]-1],matrix[R[i][j]-1][R[i-1][j]-1] = 1,1
if i+1 <= m-1 and R[i+1][j] != 0:
matrix[R[i+1][j]-1][R[i][j]-1],matrix[R[i][j]-1][R[i+1][j]-1] = 1,1
visited = [False]*num_vertex
def dfs(start):
global matrix,visited,num_vertex
visited[start] = True
for vertex in range(num_vertex):
if matrix[start][vertex] == 1 and visited[vertex] == False: dfs(vertex)
num_components = 0
while False in visited:
dfs(visited.index(False))
num_components += 1
print(num_components)
И все бы ничего, но проходит только 3 теста из 11 (пишет: Ошибка во время исполнения программы). Подскажите, в чем может быть ошибка как можно оптимизировать алгоритм, если возможно?
