Граф области в лабиринте - PullRequest
Новая
       31

Граф области в лабиринте

0 голосов
/ 25 марта 2020

Лабиринт

Напишите функцию count_areas (diagonal_maze), которая принимает диагональный лабиринт (в виде списка строк) и возвращает количество закрытых областей в диагональном лабиринте. Мы предполагаем, что по периметру лабиринта есть недиагональные границы. 

>`count_areas(["\//\\\\/", "\///\\\\", "//\\\\/\\", "\/\///"]) 
>12`

>'count_areas(["\/", "/\\"]) 
>4'

Мы делаем каждый \\ для представления только одного \, потому что синтаксис python \ особенный.

Моя идея состоит в том, чтобы взглянуть на первый ряд, а затем сравнить остальные с первым .... Однако кажется, что слишком много условий для рассмотрения.

Может кто-нибудь очистить мои логи c?

1 Ответ

0 голосов
/ 30 марта 2020

Это легко решить, используя структуру данных несвязанного набора:

Создайте набор для каждой вертикальной или горизонтальной границы - между ячейками и по краям лабиринта.

Для каждой ячейки / объедините наборы для ее верхней и левой сторон и объедините наборы для ее нижней и правой сторон.

Для каждой ячейки \ объедините наборы для ее верхней и правые стороны и соедините наборы для нижней и левой сторон.

Наконец, посчитайте количество наборов, с которыми у вас осталось - будет один для каждой области лабиринта.

...