Loading...
BobsunPower avatar BobsunPower 0 Точки

[Python Fundamentals/List Advanced/More Exercise/05.Dots]

Здравейте!
Някой може ли да ми даде насока, какъв подход се използва за решението на
[Python Fundamentals/List Advanced/More Exercise/05.Dots] ?
Готови решения също биха били полезни.
Благодаря Ви!

0
Python Fundamentals 23/07/2021 00:01:48
MartinBG avatar MartinBG 4803 Точки

Решение на подобен проблем:

Find length of the largest region in Boolean Matrix

Трябва да го адаптирате към условието на задачата (без диагоанали и '.' вместо '1'), но идеята е същата.

0
Airanchev avatar Airanchev 0 Точки

Това решение е направено с рекурсия

https://pastebin.com/v6aCU9aX

0
26/12/2024 18:18:04
valerielashvili avatar valerielashvili 34 Точки

Леко изчистена версия:

def is_dot(r, c):
    return board[r][c] == '.'

def in_bounds(r, c):
    return 0 <= r < len(board) and 0 <= c < len(board[0])

def is_wall(r, c):
    return board[r][c] in "-–"

def is_visited(r, c):
    return board[r][c] == 'v'

def find_dots_dfs(r, c):
    if not in_bounds(r, c) or is_wall(r, c) or is_visited(r, c):
        return 0

    board[r][c] = 'v'
    dot_cnt = 1
    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        dot_cnt += find_dots_dfs(r + dr, c + dc)
    return dot_cnt

# Read input
n = int(input())
board = [input().split() for _ in range(n)]

dot_cnt_max = 0
for row in range(len(board)):
    for col in range(len(board[0])):
        if is_dot(row, col):
            dot_cnt_max = max(dot_cnt_max, find_dots_dfs(row, col))

print(dot_cnt_max)

Бъдете внимателни с тази задача, защото гърми четвъртия тест с "runtime error" при неправилно направен метод за рекурсия. Ако посетените клетки не бъдат отбелязани за такива има риск програмата да се върне на една от позициите и да надвиши разрешения брой за извикване на рекурсията, която в Пайтън е 1000. С големи матрици има риск да гърми.

Също така имайте предвид, че итеративен DFS алгоритъм е по-безопасен от рекурсивния. Обаче ми гърмеше и за двата.

Сега не мога да разбера кое по-точно ми беше проблема, възможно самата рекурсия със всичките проверки вътре в нея. В тази версия на кода проверките са изнесени извън рекурсивния метод find_dots_dfs. Ако премахна проверката за стената броя на свързаните точки се объркват и всичките тестове гърмят освен четвъртия, който ми гърмеше с леко различен код.

За съжаление, нямам повече време за тестовете да открия кое точно прави проблема.

Хората блъскащи си главите да не се мислят за тъпи и да не се демотивират! Задачата няма как да се реши без да се вземе материала за матрици, рекурсии и DFS алгоритми, темите на които във Fundamentals курса едва ли се обръща достатъчно внимание, ако изобщо се споменават. Надявам се администрацията си дава сметката за това.

Подходът за решаването изисква практика и едно осмисляне на обхождането на пътеките в матриците. Успех на всички и не се ядосвайте като мен! ;) 

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.