Напишите программу Python для разделения карты на разделы.

Допустим, нам дана пара двумерных списков, содержащих какие-то числа.

map1 = [
    [0,0,0,0],
    [0,1,1,0],
    [2,2,1,0],
    [2,2,1,0],
]

Обратите внимание, что внутри 2d-списка есть разные числа. Напишите функцию section(map), которая принимает список 2d и возвращает группы чисел, которые связаны друг с другом.

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

{
    0: [
        {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3)}
    ],
    1: [
        {(1,2), (3,2), (1,1), (2,2)} 
    ],
 
    2: [
        {(3,0), (2,0), (3,1), (2,1)}
    ]
}

Словарь, в котором каждый ключ представляет собой число, а каждое значение представляет собой список наборов координат, каждый набор представляет собой участок с цветовой кодировкой. Каждый номер может иметь более 1 раздела:

map2 = [
    [0,0,0,1],
    [0,1,1,0],
    [2,2,1,0],
    [2,2,1,0],
]

В map2 только 1 число изменено с map1, но это делит секцию 0 на 2. Что возвращает наша функция:

{
    0: [
        {(0,1), (1,0), (0,0), (0,2)},
        {(1,3), (2,3), (3,3)}
    ],

    1: [
        {(0,3)},
        {(1,2), (3,2), (1,1), (2,2)}
    ],
 
    2: [
        {(3,0), (2,0), (3,1), (2,1)}
    ]
}

Логика решения

Давайте разделим это на несколько шагов, чтобы упростить задачу:

  • Учитывая координату, найти все связанные координаты с тем же значением
  • Повторение этого шага для каждой непосещенной координаты

1. По заданной координате найти все связанные координаты с одинаковым значением.

Например, учитывая координату (3,0) (текущая координата) со значением 2 (текущее значение), найдите все другие координаты со значением 2, которые связаны с (3,0). (Двойки обведены зеленым на диаграмме выше)

Вещи, которые нам нужно отслеживать:

  • Очередь queue для хранения координат, которые мы хотим найти
  • Набор same_val для отслеживания, какие координаты мы искали
  1. Инициализируйте queue, чтобы он содержал нашу заданную координату
  2. Выньте первую координату из queue и добавьте ее в same_val
  3. Поиск в 4 направлениях (вверх, вниз, влево, вправо) от этой координаты
  4. Добавить новые координаты обратно в очередь, если значение в новой координате равно текущему значению
  5. Повторяйте шаги со 2 по 4, пока queue не станет пустым.

В конце этих 5 шагов same_val будет содержать все остальные координаты с тем же значением, которые связаны с текущей координатой.

Выполнение этого шага

Допустим, нам дана координата (0,0). Таким образом инициализируются следующие переменные:

queue = [(0,0)]
same_val = set()

Итерация 1 — поиск (0, 0)

same_val = {(0,0)}
queue = [(1,0), (0,1)]

Убираем первую координату из queue, ищем в 4 направлениях любые связанные с ней координаты того же значения и добавляем их в queue

Итерация 2 — поиск (1, 0)

same_val = {(0,0), (1,0)}
queue = [(0,1)]

В этой итерации мы ничего не добавляем к queue, так как ни одна из 4 координат вокруг координаты (1,0) недействительна. (0,0) действителен, но мы его уже искали.

Итерация 3 — поиск (0, 1)

same_val = {(0,0), (1,0), (0,1)}
queue = [(0,2)]

Поиск по 4 направлениям вокруг (0,1) порождает новую допустимую неисканную координату (0,2), поэтому мы добавляем (0,2) к queue.

Следующие несколько итераций

(0,2) порождает (0,3), (0,3) порождает (1,3), и так продолжается до тех пор, пока не останется связанных координат с тем же значением. В конечном итоге мы получаем это:

same_val = {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3)}

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

Как только мы сможем найти все связанные координаты с одинаковым значением для одной координаты, мы можем повторить это для каждой другой координаты. Мы просто должны быть внимательны, чтобы не искать координаты, о которых уже известно, что они являются частью существующего раздела. Мы можем добиться этого, используя набор.

Кодовое решение

Выполнение этого шага

Итерация 1 — поиск (0, 0)

Поиск (0,0) порождает следующий набор связанных координат с тем же значением 0.

same_val = {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3)}

Затем мы добавляем все значения здесь к seen, так как поиск любого из этих значений даст нам один и тот же набор.

seen = {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3)}

Итерация 2 — Поиск (0, 1)

Поскольку (0,1) уже находится в seen, мы игнорируем это и переходим к следующей итерации.

Итерация с 3 по 5 — Поиск (0,2), (0,3) и (1,0)

Эти 3 координаты уже есть в seen, поэтому мы их игнорируем

Итерация 6 — Поиск (1, 1)

Поиск координаты (1,1) дает нам следующий набор связанных координат с тем же значением 1:

same_val = {(1,1), (1,2), (2,2), (3,2)}

Все эти значения возвращают один и тот же набор при поиске, поэтому мы добавляем все эти значения к seen.

seen = {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3), (1,1), (1,2), (2,2), (3,2)}

Итерации с 7 по 8 — Поиск (1, 2) и (1, 3)

Эти координаты уже есть в seen, поэтому мы их игнорируем

Итерация 9 — Поиск (2, 0)

Поиск (2,0) порождает следующий набор связанных координат с тем же значением 2:

same_val = {(2,0), (2,1), (3,0), (3,1)}

Таким образом, мы добавляем все эти значения к seen

seen = {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3), (1,1), (1,2), (2,2), (3,2), (2,0), (2,1), (3,0), (3,1)}

Все итерации после этого

Все возможные координаты уже находятся в seen, поэтому мы игнорируем все остальное. Таким образом, в конце всех итераций мы получаем наш вывод:

{
    0: [
        {(0,1), (0,0), (1,3), (3,3), (2,3), (1,0), (0,2), (0,3)}
    ],
1: [
        {(1,2), (3,2), (1,1), (2,2)} 
    ],
 
    2: [
        {(3,0), (2,0), (3,1), (2,1)}
    ]
}

Заключение

Я пишу статьи по программированию (раз в 1–2 дня), которые, вероятно, помогли бы мне в более молодом возрасте ускорить процесс обучения. Присоединяйтесь к моему списку адресов электронной почты, чтобы получать уведомления о каждой публикации.



Получать электронное письмо каждый раз, когда Zlliu публикует.
Получать электронное письмо, когда Zlliu публикует. Зарегистрировавшись, вы создадите учетную запись Medium, если у вас ее еще нет…zl-liu.medium.com



Если эта статья была полезной и вы хотите поддержать меня, подумайте о том, чтобы подписаться на членство в Medium — это стоит 5 долларов в месяц, и вы получаете неограниченный доступ к статьям на Medium. Если вы зарегистрируетесь по моей ссылке ниже, я получу небольшую комиссию без каких-либо дополнительных затрат для вас.

Зарегистрируйтесь, используя мою ссылку здесь, чтобы читать неограниченное количество статей на Medium.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.