A rectangular garden plot of width N and length M of meters is divided into squares with a side of 1 meter. On this site beds are dug up. A bed is a set of squares that satisfies such conditions:

- from any square of this bed you can get into any other square of the same bed,

-consistently moving along the row from square to square through their common side;

-No two beds do not intersect and do not touch each other either on the vertical or horizontal sides of the squares (touching the beds by the corners of the squares is allowed).

Count the number of beds in the garden.

Input data:

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

Additional modules do not use.

The first line contains the numbers N and M separated by a space, followed by N lines with M characters. The symbol # indicates the territory of the beds, the dot corresponds to the unoccupied territory. No other characters. (1 ≤ N, M ≤ 200)

The main problem is that the code is checked on the site , where it is checked on 12 tests. Test conditions are not specified, but at the same time they all fail to pass ...

My best bet: 11 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. Thanks for attention)

  • Correct the formatting of the code in question, because of the indentations that went, the code given is not valid for Python. - Yaant
  • (previous comment edited, removed erroneous information). - Yaant

1 answer 1

To simplify conditions in dfs() , you can surround the site with empty squares. Otherwise, the algorithm is the same as in the first example in the question:

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

Solution head-on (small input numbers). I did not check on the site, you can compare with your code for different entries:

 #!/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))