How do you bend 2D grid to a toroid and count the adjacent field of same characters?

  Kiến thức lập trình

I have a grid with S columns and V rows that cointains only “.” or “#” signs . How can I write a Python programme that would count how many groups of “.” signs emerge adjacent to each other if the grid is bent to a shape of a single hole toroid? If there is a single “.” surrounded by “#” signs it is to be regarded as a group. It is important to know that when the grid is folded to a shape of a toroid, grids edges become adjacent to each other. Input begins with number S, which states how many columns grid has and number V which states how many rows it has. Then the grid itself follows. I need the programme to be able to map any grid with this descrition. I’ve tried to use BlackBox AI and it didn!t help at all. Maybe it made things worse.
I have 2 inputs I am going to give you bellow and I know that the correct anwer to both of them is 4.
The inputs are:
8 6
.#…##.
#.##.#.#
.#.#..#.
##.#..##
….#.#.
#…#.#.
And
9 9
.#..#..#.
#…###.#
..##…..
..#….#.
.##..#.#.
..###…#
#.###..#.
##.#.#..#
.#..#…#

The code I have so far always gives wrong answer. Most of the times it gives numeber that is 1 bigger or lesser than the right answer.
Here is the code:

def is_valid(x, y, S, V):
    return 0 <= x < S and 0 <= y < V

def dfs(grid, x, y, S, V, visited):
    if grid[y][x] != '.':
        return

    visited[y][x] = True

    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
        nx, ny = (x + dx + S) % S, (y + dy + V) % V
        if is_valid(nx, ny, S, V) and not visited[ny][nx]:
            dfs(grid, nx, ny, S, V, visited)

def count_groups(grid, S, V):
    visited = [[False] * S for _ in range(V)]

    count = 0

    for y in range(V):
        for x in range(S):
            if grid[y][x] == '.' and not visited[y][x]:
                dfs(grid, x, y, S, V, visited)
                count += 1

    return count

def main():
    S, V = map(int, input().split())
    grid = [list(input()) for _ in range(V)]

    print(count_groups(grid, S, V))

I’ve been working on this for 4 days and I tried many different versions. I asked AI for help but I feel like it only made things worse. In the begining I tried to write simpler code that would append frist line of input uder the last line and that search the code for neighbouring signs. Than I tried to do the same for breadh but now I am completely lost…

New contributor

Ondřej Dzius is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

LEAVE A COMMENT