#python #recursion #gaps-and-islands
#python #рекурсия #пробелы и острова
Вопрос:
Я решаю проблему нахождения размеров всех островов, существующих в матрице nxm. Я использовал рекурсивный метод и понятия не имею, какая ошибка в моем коде вызывает ошибку максимальной глубины рекурсии. Заранее благодарю вас 🙂
def riverSizes(matrix):
returnList = []
for row in range(len(matrix)):
for column in range(len(matrix[row])):
if matrix[row][column] == 1:
returnList.append(visitConnected(matrix,row,column))
def visitConnected(matrix,row,column,size=0):
if inBounds(row,column,matrix):
if matrix[row][column] == 1:
matrix[row][column] == -1
size = 1
size = visitConnected(matrix,row 1,column)
size = visitConnected(matrix,row - 1,column)
size = visitConnected(matrix,row,column 1)
size = visitConnected(matrix,row,column-1)
else:
return size
else:
return size
def inBounds(row,column,matrix):
return row >= 0 and row < len(matrix) and column >= 0 and column < len(matrix[0])
Ответ №1:
Не видя примеров или вызова, я вижу хотя бы одну проблему. Рассмотрим матрицу [[1, 1]] . visitConnected(..., 0, 0) вызовет size = visitConnected(..., 0, 1) , который вызовет size = visitConnected(..., 0, 0) , поэтому вы никогда не завершите работу.
Вы пишете matrix[row][column] == -1 вместо matrix[row][column] = -1 , поэтому там ничего не происходит. Вы также не возвращаете окончательный размер, поэтому ваш список возврата будет all None .
Комментарии:
1. В моем коде есть строка с надписью matrix [строка] [столбец] = -1, поэтому код знает, что он уже был посещен, и, в свою очередь, не повторяет его снова, я неправильно реализовал эту строку?
2. Нет, эта строка ничего не устанавливает, что является основной причиной. Ваша функция не возвращает вычисляемый размер, что будет другой проблемой.
3. Я убедился, что он возвращает размер каждого из шагов повторения, которые он выполняет, не меняется ли значение 1 на -1, когда я опускаюсь на уровень глубины?
4. Проверьте мой ответ, у вас опечатка.