Обход массива в глубину: код подсчёта количества грядок на садовом участке не проходит тесты на сайте

#python #массивы #алгоритм #python_3x

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

-из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки,

-последовательно переходя по грядке из квадрата в квадрат через их общую сторону;

-никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, 
ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).

Подсчитайте количество грядок на садовом участке.

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

5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.


Дополнительные модули не использовать.

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



Основная проблема, в том, что код проверяется на сайте, где он проверяется по 12
тестам. Условия тестов не указаны, но одновременно их все пройти не получается...

мой лучший вариант: 11 из 12:

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)


есть еще: 10 из 12:

def solve1(N, M, case):
    l = [[0] * M for i in range(N)]
    n = 0
    connected = set()
    for i in range(N):
        for j in range(M):
            x = 0
            if case[i][j] == '#': 
                if (i > 0 and l[i-1][j] != 0):
                    x = l[i-1][j]
                left = l[i][j-1]
                if (j > 0 and left != 0):
                    if x != left:
                        if x > 0:
                            connected.add(frozenset((x, left)))
                        else:
                            x = left
                if x == 0:
                    n += 1
                    x = n
                l[i][j] = x
#print('\n'.join(str(r) for r in case))
#print('\n'.join(str(r) for r in l))
#print(connected)
    return n - len(connected)

N, M = map(int, input().split()) 
case = [ list(input()) for _ in range(N) ]
print(solve1(N, M, case))


Был бы рад конструктивной критике. Спасибо за внимание)
    

Ответы

Ответ 1

Чтобы упростить условия в dfs(), можно окружить участок пустыми квадратами. Иначе
алгоритм такой же как в первом примере в вопросе: 

Проверяем принадлежит ли квадрат ещё непосещённой грядке
    Посещаем все квадраты, принадлежащие этой грядке
Повторяем пока все квадраты в огороде не проверим.


Решение в лоб (числа входные маленькие). Не проверял на сайте, можете со своим кодом
для разных вводов сравнить:

#!/usr/bin/env python3
BED = '#'  # mark garden bed
WEST, NORTH, EAST, SOUTH = (-1, 0), (0, -1), (1, 0), (0, 1) # directions

# read input
N, M = map(int, input().split())
garden = [input().strip() for _ in range(N)]

# surround the garden with empty squares
garden[:] = [' '*(M+2)] + [' ' + row + ' ' for row in garden] + [' '*(M+2)]

def visit_garden_bed(i, j, seen):
    """Enumerate all garden bed's squares"""
    q = [(i, j)]
    while q:
        i, j = vertex = q.pop()
        seen.add(vertex)
        for dx, dy in [WEST, NORTH, EAST, SOUTH]: # all possible directions
            y, x = vertex = (i+dy, j+dx)
            if garden[y][x] == BED and vertex not in seen:
                q.append(vertex)
    return 1 # the number of garden beds visited

# visit all garden beds
seen = set() # (i, j)
print(sum(visit_garden_bed(i, j, seen)
          for i, row in enumerate(garden)
          for j, square in enumerate(row)
          if square == BED and (i, j) not in seen))