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

@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.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

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