Обход в глубину (задача на количество грядок)

@indablackk · Регистрация: 07.10.2015

Студворк — интернет-сервис помощи студентам

Прошу помочь с решением задачи, как уже только не возился с этим кодом, даже не представляю в чем подвох.
Для входных данных в примере ниже код работает, но автоматическая проверка на 11 тестов (видов входных данных) не проходит.
Какие они, эти 11 тестов, не знаю и не могу узнать.

Источник
Условие:
Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ N, M ≤ 200.

Выходные данные
Вывести одно число - количество грядок на садовом участке.

Пример
Входные данные:

Python
1
2
3
4
5
6
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

Выходные данные:
5

Мой код (Прошел 6 тестов из 11, остальные 5 - ошибка)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n, m = input().split()
n = int(n)
m = int(m) 
alll = [[] for i in range(n)]
visited = [[False for j in range(m)] for i in range(n)]
num = 0 
 
for i in range(n):
    row = list(input())
    for j in range(m):
        alll[i].append(row[j])
 
def dfs(x, y):
    visited[x][y] = True
    for dx, dy in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
        if  (0 <= (x + dx) < n) and (0 <= (y + dy) < m): 
            if alll[x + dx][y + dy] != "." and not visited[x + dx][y + dy]:
                dfs(x + dx, y + dy)
          
for x in range(n):
    for y in range(m):
        if alll[x][y] != "." and not visited[x][y]:
            dfs(x, y)
            num += 1
 
print(num)

Мой тупой код (Прошел 10 тестов из 11, оставшийся 1 - неправильный результат)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
try:
    n, m = input().split()
    n = int(n)
    m = int(m)
    alll = [[] for i in range(n)]
    visited = [[False for j in range(m)] for i in range(n)]
    num = 0 
 
    for i in range(n):
        row = list(input())
        for j in range(m):
            alll[i].append(row[j])
 
    def dfs(x, y):
        visited[x][y] = True
        for dx, dy in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
            if  0 <= x + dx <= n-1 and 0 <= y + dy <= m-1: 
                if alll[x + dx][y + dy] == "#" and not visited[x + dx][y + dy]:
                    dfs(x + dx, y + dy)
          
    for x in range(n):
        for y in range(m):
            if alll[x][y] == "#" and not visited[x][y]:
                dfs(x, y)
                num += 1
except Exception:
    num += 1
 
print(num)

@dondublon · 08.10.2015, 08:21

У вас найденные грядки помечаются как bool. Почему? По идее, их надо нумеровать.

Я бы сделал так:
(Делаю через массивы numpy, потому что так привычнее, можно делать сразу двумерную индексацию.)
arr - наш массив, содержит 1 и 0, грядка или нет. buf - буфер для номеров грядок, такого же размера, его заполняем по ходу дела.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import numpy as np
data0="""
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
"""
 
arr = np.frombuffer(data0, dtype=np.int8)
arr = arr[arr>20].reshape((5, 10))
arr[arr==35]=1
arr[arr==46]=0
print arr
 
buf = np.zeros(arr.shape)-1
# -1 - unchecked
# 0 - no area
# 1..n - area number
 
def mark_area(arr, buf, i, j, mark):
    if i < 0 or j < 0 or i >= arr.shape[0] or j >= arr.shape[1]:
        return False
    if not arr[i, j]:
        return False
    if buf[i, j] == -1:
        buf[i, j] = mark
        mark_area(arr, buf, i-1, j, mark)
        mark_area(arr, buf, i+1, j, mark)
        mark_area(arr, buf, i, j-1, mark)
        mark_area(arr, buf, i, j+1, mark)
        return True
    else:
        return False
 
counter = 1
for i in xrange(arr.shape[0]):
    for j in xrange(arr.shape[1]):
        if mark_area(arr, buf, i, j, counter):
            counter += 1
 
print buf
print np.max(buf)

@Vtulhu · 08.10.2015, 17:15

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(raw_input().split(' ', 1)[0])
field = [ list(raw_input()) for _ in xrange(n) ]
m = len(field[0])
 
beds = 0
 
for x in xrange(n):
    for y in xrange(m):
        if field[x][y] == '#':
            beds += 1
            stack = [ (x, y) ]
            while len(stack) != 0:
                x, y = stack.pop()
                if x >= 0 and x < n and y >= 0 and y < m and field[x][y] == '#':
                    field[x][y] = '.'
                    stack.append((x + 1, y))
                    stack.append((x - 1, y))
                    stack.append((x, y - 1))
                    stack.append((x, y + 1))
 
print(beds)

@indablackk · 08.10.2015, 19:53 **[ТС]**

dondublon, с таким модулем мне, видимо, еще предстоит ознакомиться)
К сожалению, сработало ли решение сказать не могу, т.к. автоматическая проверка на сайте предполагает код без модулей.
Благодарю за отклик

Добавлено через 6 минут
Vtulhu, довольно интересная и новая для меня реализация обхода в глубину.
Благодарю. Запомню ее на будущее

Результат проверки твоего кода меня не сильно удивил : 7 из 11 тестов (оставшиеся тесты напоролись на ошибку)
Видимо, лажает, скорее всего, автоматическая проверка, а не код. Или я чего то недопонимаю.

@Vtulhu · 09.10.2015, 00:53

Сообщение от indablackk

Vtulhu, довольно интересная и новая для меня реализация обхода в глубину.

Вы не поверите - в Википедии нашел.

Сообщение от indablackk

Результат проверки твоего кода меня не сильно удивил : 7 из 11 тестов (оставшиеся тесты напоролись на ошибку)
Видимо, лажает, скорее всего, автоматическая проверка, а не код. Или я чего то недопонимаю.

Скорее всего, дело в этом:

Ограничение по времени, сек 1
Ограничение по памяти, мегабайт 64

Вот я попытался немного оптимизировать...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = int(raw_input().split(' ', 1)[0])
field = [ list(raw_input()) for _ in xrange(n) ]
m = len(field[0])
 
beds = 0
stack = set()
 
for x in xrange(n):
    for y in xrange(m):
        if field[x][y] == '#':
            beds += 1
            stack.clear()
            stack.add( (x, y) )
            while len(stack) != 0:
                x, y = stack.pop()
                if field[x][y] == '#':
                    field[x][y] = '.'
                    if x != 0:     stack.add( (x - 1, y) )
                    if x != n - 1: stack.add( (x + 1, y) )
                    if y != 0:     stack.add( (x, y - 1) )
                    if y != m - 1: stack.add( (x, y + 1) )
 
print(beds)

@dondublon · 09.10.2015, 07:01

Сообщение от indablackk

dondublon, с таким модулем мне, видимо, еще предстоит ознакомиться)

Там ничего сложного.
Просто у меня двумерный массив, а у вас - список списков. Вместо arr[i,j] пишите arr[i][j], а заполняйте своим способом.
Не отвлекайтесь на модуль, главная идея в том, что грядки надо нумеровать, а не помечать через bool.

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@indablackk 0 / 0 / 0 Регистрация: 07.10.2015 Сообщений: 2
	08.10.2015, 19:53 [ТС]
	dondublon, с таким модулем мне, видимо, еще предстоит ознакомиться) К сожалению, сработало ли решение сказать не могу, т.к. автоматическая проверка на сайте предполагает код без модулей. Благодарю за отклик Добавлено через 6 минут Vtulhu, довольно интересная и новая для меня реализация обхода в глубину. Благодарю. Запомню ее на будущее Результат проверки твоего кода меня не сильно удивил : 7 из 11 тестов (оставшиеся тесты напоролись на ошибку) Видимо, лажает, скорее всего, автоматическая проверка, а не код. Или я чего то недопонимаю. 0