Question:
A rectangular garden plot N meters wide and M meters long is divided into squares with a side of 1 meter. Beds have been dug up in this area. A bed is a collection of squares that satisfies the following conditions:
– from any square of this bed you can get to any other square of the same bed,
– successively moving along the bed from square to square through their common side;
– no two beds intersect and do not touch each other either on the vertical or horizontal sides of the squares (touching the beds with the corners of the squares is allowed).
Count the number of beds in the garden plot.
Input data:
5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.
Do not use additional modules.
The first line contains the numbers N and M separated by a space, followed by N lines of M characters each. The symbol # denotes the territory of the beds, the dot corresponds to the unoccupied territory. There are no other characters. (1 ≤ N, M ≤ 200)
The main problem is that the code is checked on the site , where it is checked against 12 tests. The conditions of the tests are not specified, but it is impossible to pass them all at the same time …
my best option: 11 out of 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)
there are more: 10 out of 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))
I would be glad to constructive criticism. Thank you for your attention)
Answer:
To simplify the conditions in dfs() , you can surround the plot with empty squares. Otherwise, the algorithm is the same as in the first example in the question:
Проверяем принадлежит ли квадрат ещё непосещённой грядке
Посещаем все квадраты, принадлежащие этой грядке
Повторяем пока все квадраты в огороде не проверим.
Head-on solution (input numbers are small). I didn’t check it on the site, you can compare with your code for different inputs:
#!/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))