Подсчет незащищенных ячеек в сетке (рекурсия) ⇐ Python
-
Anonymous
Подсчет незащищенных ячеек в сетке (рекурсия)
Это полупопулярный вопрос о литкоде. И я знаю, что в Интернете есть много решений, но я практикуюсь, решая все эти проблемы самостоятельно, чтобы по-настоящему освоить рекурсию. Мне интересно, что не так с моим нынешним подходом; Я продолжаю расширять стек вызовов. Буду признателен за обратную связь! Вот вопрос:
"Вам даны два целых числа m и n, представляющие сетку m x n с индексом 0. Вам также даны два двумерных целочисленных массива Guards и Walls, где Guards = [rowi, coli] и Walls[j] = [rowj , colj] представляют позиции i-го охранника и j-й стены соответственно.
Охранник может видеть каждую клетку в четырех основных направлениях (север, восток, юг или запад), начиная со своей позиции, если ему не мешает стена или другой охранник. Ячейка охраняется, если есть хотя бы один охранник, который может ее видеть.
Вернуть количество незанятых ячеек, которые не охраняются.
Пример
Ввод:
m = 4, n = 6, охранники = [[0,0],[1,1],[2,3]], стены = [[0,1],[2,2] ,[1,4]] Выход:
"7" Вот код, который я написал на данный момент:
def countUnguarded(m: int, n: int, Guards: List[List[int]], wall: List[List[int]]) -> int: def dfs(сетка, строка, столбец): если строка = m или столбец < 0 или столбец >= n или сетка[строка][столбец] == 'W': возвращаться # Отметить ячейку как просмотренную печать("маркировка") сетка[строка][столбец] = '1' # Рекурсивный вызов dfs(сетка, строка + 1, столбец) dfs(сетка, строка - 1, столбец) dfs(сетка, строка, столбец + 1) dfs(сетка, строка, столбец - 1) сетка = [['0'] * n для _ в диапазоне (м)] # Обновите сетку, чтобы пометить охранников буквой «G». для охраны в гвардии: строка, столбец = охранник сетка[строка][столбец] = 'G' # Обновить сетку, чтобы пометить стены буквой W. для стены в стене: строка, столбец = стена сетка[строка][столбец] = 'W' # Запускаем dfs для каждой ячейки с помощью Guard для строки в диапазоне (м): для столбца в диапазоне (n): если сетка[строка][столбец] == 'G': print(f"запуск DFS в точке {row, col}") dfs(сетка, строка, столбец) # результат подсчета неохраняемый_счет = 0 для строки в диапазоне (м): для столбца в диапазоне (n): если сетка[строка][столбец] == '0': unguarded_count += 1 вернуть unguarded_count
Это полупопулярный вопрос о литкоде. И я знаю, что в Интернете есть много решений, но я практикуюсь, решая все эти проблемы самостоятельно, чтобы по-настоящему освоить рекурсию. Мне интересно, что не так с моим нынешним подходом; Я продолжаю расширять стек вызовов. Буду признателен за обратную связь! Вот вопрос:
"Вам даны два целых числа m и n, представляющие сетку m x n с индексом 0. Вам также даны два двумерных целочисленных массива Guards и Walls, где Guards = [rowi, coli] и Walls[j] = [rowj , colj] представляют позиции i-го охранника и j-й стены соответственно.
Охранник может видеть каждую клетку в четырех основных направлениях (север, восток, юг или запад), начиная со своей позиции, если ему не мешает стена или другой охранник. Ячейка охраняется, если есть хотя бы один охранник, который может ее видеть.
Вернуть количество незанятых ячеек, которые не охраняются.
Пример
Ввод:
m = 4, n = 6, охранники = [[0,0],[1,1],[2,3]], стены = [[0,1],[2,2] ,[1,4]] Выход:
"7" Вот код, который я написал на данный момент:
def countUnguarded(m: int, n: int, Guards: List[List[int]], wall: List[List[int]]) -> int: def dfs(сетка, строка, столбец): если строка = m или столбец < 0 или столбец >= n или сетка[строка][столбец] == 'W': возвращаться # Отметить ячейку как просмотренную печать("маркировка") сетка[строка][столбец] = '1' # Рекурсивный вызов dfs(сетка, строка + 1, столбец) dfs(сетка, строка - 1, столбец) dfs(сетка, строка, столбец + 1) dfs(сетка, строка, столбец - 1) сетка = [['0'] * n для _ в диапазоне (м)] # Обновите сетку, чтобы пометить охранников буквой «G». для охраны в гвардии: строка, столбец = охранник сетка[строка][столбец] = 'G' # Обновить сетку, чтобы пометить стены буквой W. для стены в стене: строка, столбец = стена сетка[строка][столбец] = 'W' # Запускаем dfs для каждой ячейки с помощью Guard для строки в диапазоне (м): для столбца в диапазоне (n): если сетка[строка][столбец] == 'G': print(f"запуск DFS в точке {row, col}") dfs(сетка, строка, столбец) # результат подсчета неохраняемый_счет = 0 для строки в диапазоне (м): для столбца в диапазоне (n): если сетка[строка][столбец] == '0': unguarded_count += 1 вернуть unguarded_count
