malkovsky May 8 2020 at 02:01

Замощение доминошками

13 min

8.4K

Одна из первых действительно интересных задач по математике, с которыми я столкнулся формулируется так: "из шахматной доски вырезали две противоположные по диагонали угловые клетки, можно ли оставшуюся часть разрезать на "доминошки" — фигурки из двух клеток, у которых одна сторона общая?". У нее очень простая формулировка, в отличие от великой теоремы Ферма она имет простое, элегантное, но неочевидное решение (если вы знаете решение задачи, то попробуйте применить его к фигуре справа).

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

Nota bene! Материал этой статьи — это усеченный вариант вот этого jupyter-notebook, все картинки и анимации, которые вы увидите в статье, сгенерированы кодом из этого ноутбука (правда анимаций не будет в github предпросмотре). К слову, картинки из заголовка также сгенерированы с помощью python/matplotlib

Вспомогательный код для отрисовки, он еще пригодится

import matplotlib.pyplot as plt
from matplotlib import colors as mcolors
colors = dict(mcolors.BASE_COLORS, **mcolors.CSS4_COLORS)

# Sort colors by hue, saturation, value and name.
by_hsv = sorted((tuple(mcolors.rgb_to_hsv(mcolors.to_rgba(color)[:3])), name)
                for name, color in colors.items())
names = [name for hsv, name in by_hsv if name not in {'black', 'k', 'w', 'white', 'crimson', 'royalblue', 'limegreen', 'yellow', 'orange'}]
import random
random.shuffle(names)
names = ['crimson', 'royalblue', 'limegreen', 'yellow', 'orange', *names]
names.append('red')
names.append('white')
names.append('black')

def fill_cell(i, j, color, ax):
    ax.fill([i, i, i + 1, i + 1, i], [j, j + 1, j + 1, j, j], color=color)

def draw_filling(filling):
    if filling is not None:
        n = len(filling)
        m = len(filling[0])
        fig = plt.figure(figsize=(m * 0.75, n * 0.75))

        ax = fig.add_axes([0, 0, 1, 1])
        ax.get_xaxis().set_visible(False)
        ax.get_yaxis().set_visible(False)      

        for name, spine in ax.spines.items():
            spine.set_visible(False)
            spine.set_visible(False)

        for i, row in enumerate(filling):
            i = n - i - 1
            for j, cell in enumerate(row):
                fill_cell(j, i, names[cell], ax)

        for i in range(n + 1):
            ax.plot([0, m], [i, i], color='black')
        for i in range(m + 1):
            ax.plot([i, i], [0, n], color='black')
        plt.close(fig)
        return fig
    else:
        return None

Прежде, чем перейти дальше, решение исходной задачи

Сделать это невозможно, и этому есть красивое и простое объяснение:

На оставшейся части доски 30 черных и 32 белых клетки
Каждая доминошка состоит из одной черной и одной белой клетки
Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток

Динамическое программирование по профилю

Про динамического программирования есть статья на хабре, которая даже содержит пример с покрытием доминошками, я немного расширю этот пример.

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

$F_{n+1}=F_n+F_{n-1}.$

Аналогично можно вычислить число "сочетаний" $inline$ , воспользовавшись одним из следующих рекуррентных соотношений

$C_n^k=\frac{n}{k}C_{n-1}^{k-1},$

$C_n^k=C_{n-1}^k+C_{n-1}^{k-1}.$

Для задачи "можно ли замостить доминошками прямоугольник $n\times m$ ?" к сожалению подобных простых соотношений не существует. Тем не менее, если мы рассмотрим более широкий класс фигурок, то такие соотношения уже станут возможными, главное чтобы это не были слишком маленькие классы и динамическое программирование не превратилось в банальный перебор.

Посмотрим на следующий класс фигурок: у нас есть прямоугольник $(k-1)\times m$ , на строке $inline$ присутствуют первые $inline$ клеток, остальные задаются профилем, на строке $inline$ первые $inline$ клеток задаются профилем, остальные не участвуют. Профиль — это последовательность нулей и единичек длины $inline$ : если на $inline$ -ой позиции профиля единичка, это значит что в этой фигуре есть соответствующая клетка, всего профилей $inline$ (красные клетки — единички, синие — нули).

Профиль однозначно задается числом $inline$ (его бинарное представление вплоть до $inline$ разрядов является последовательностей нулей и единичек).

Прямоугольник $n\times m$ соответствует фигуре с $inline$ , $inline$ и нулевым профилем. На фигурках такого типа мы можем считать две основные функции

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

Давайте обозначим за $inline$ количество способов замостить такую фигурку, тогда $inline$ и при этом $inline$ выражается через сумму нескольких $g(k, j-1, m, \cdot)$ , по большому счету переход от $inline$ к $inline$ — это перебор трех случаев: поставить вертикальную доминошку, если это возможно

горизонтальную доминошку, если это возможно

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

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

tiling = [
    '........',
    '........',
    '........',
    '........',
    '........',
    '........',
    '........',
    '........',
]

Начнем с

количества способов замощений доминошками

def count_tilings(tiling):
    n = len(tiling)
    m = len(tiling[0])
    if ((n + 1) * m * 2 ** m) <= 10000000:
        dp = [[[(0 if k != 0 or j != 0 or mask != 0 else 1) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]
    for k in range(n):
        for j in range(m):
            for mask in range(2 ** m):
                # Вертикальная доминошка
                if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &  (1 << j)) == 0:
                    dp[k + ((j + 1) // m)][(j + 1) % m][mask + (1 << j)] += dp[k][j][mask]
                # Горизонтальная доминошка
                if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:
                    dp[k + ((j + 1) // m)][(j + 1) % m][mask + (2 << j)] += dp[k][j][mask]
                # Клетка занята
                if ((1 << j) &  mask) != 0 or tiling[k][j] != '.':
                    dp[k + ((j + 1) // m)][(j + 1) % m][(mask | (1 << j)) - (1 << j)] += dp[k][j][mask]
    return dp

dp = count_tilings(tiling)
print(dp[8][0][0])

получаем

12988816

Сверяемся с википедией, пока все в порядке. Давайте еще на всякий случай проверим, количество способов замостить полоску $n\times 2$ — должно получиться число Фибоначчи.

tiling_fib = [
    '..',
    '..',
    '..',
    '..',
    '..',
    '..',
    '..',
    '..'
]
dp = count_tilings(tiling_fib)
for i in range(8):
    print(dp[i][0][0], end=' ')

1 1 2 3 5 8 13 21

Что ж, поехали дальше, проверим на доске с вырезанными углами

tiling_no_corners_opposite = [
    '.......#',
    '........',
    '........',
    '........',
    '........',
    '........',
    '........',
    '#.......',
]
dp = count_tilings(tiling_no_corners_opposite)
print(dp[8][0][0])

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

код для получения покрытия

def cover_if_possible(tiling, dp=None):
    if dp is None:
        dp = count_tilings(tiling)
    n = len(dp) - 1
    m = len(dp[0])
    if dp[n][0][0] == 0:
        return None

    result = [[-1 if tiling[i][j] == '#' else 0 for j in range(m)] for i in range(n)]
    num = 0

    k = n
    j = 0
    mask = 0

    while k > 0 or j > 0:
        #print(k, j, mask)
        prev_j = j - 1
        prev_k = k
        if prev_j == -1:
            prev_j += m
            prev_k -= 1

        # Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask
        # Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее 
        # самого подсчета динамики
        for prev_mask in range(2 ** m):
            if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \
                (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and dp[prev_k][prev_j][prev_mask] != 0:
                mask = prev_mask
                result[prev_k][prev_j] = num
                result[prev_k + 1][prev_j] = num
                #print(f'Vertical at ({prev_k}, {prev_j}) ({prev_k + 1}, {prev_j})')
                num += 1
                break
            elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and \
                prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:
                mask = prev_mask
                result[prev_k][prev_j] = num
                result[prev_k][prev_j + 1] = num
                #print(f'Horisontal at ({prev_k}, {prev_j}) ({prev_k}, {prev_j + 1})')
                num += 1
                break
            elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \
                (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:
                mask = prev_mask
                break

        j = prev_j
        k = prev_k

    return result

filling = cover_if_possible(tiling)
draw_filling(filling)

Слишком просто, давайте вырежем несколько клеток

tiling_random = [
    '........',
    '#.#.....',
    '..#.....',
    '........',
    '........',
    '........',
    '........',
    '...#....'
]
filling_random = cover_if_possible(tiling_random)
draw_filling(filling_random)

Попробуем теперь сделать тоже самое для замощения максимальной возможной части фигуры

Код для максимального замощения

def maxmimum_cover(tiling):
    n = len(tiling)
    m = len(tiling[0])
    if ((n + 1) * m * 2 ** m) <= 10000000:
        dp = [[[(n * m if k != 0 or j != 0 or mask != 0 else 0) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]
    for k in range(n):
        for j in range(m):
            for mask in range(2 ** m):
                next_k, next_j = k + ((j + 1) // m), (j + 1) % m
                # Вертикальная доминошка
                if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &  (1 << j)) == 0:
                    dp[next_k][next_j][mask + (1 << j)] = min(dp[next_k][next_j][mask + (1 << j)], dp[k][j][mask])
                # Горизонтальная доминошка
                if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:
                    dp[next_k][next_j][mask + (2 << j)] = min(dp[next_k][next_j][mask + (2 << j)], dp[k][j][mask])
                # Клетка занята
                if ((1 << j) &  mask) != 0 or tiling[k][j] != '.':
                    dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = \
                        min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask])
                # Клетка не занята, рассмотриваем случай её пропуска
                else:
                    dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = \
                        min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask] + 1)
    return dp

def cover_maximum_possible(tiling, dp=None):
    if dp is None:
        dp = maxmimum_cover(tiling)
    n = len(dp) - 1
    m = len(dp[0])

    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]
    num = 0

    k = n
    j = 0
    mask = 0

    while k > 0 or j > 0:
        #print(k, j, mask)
        prev_j = j - 1
        prev_k = k
        if prev_j == -1:
            prev_j += m
            prev_k -= 1

        # Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask
        # Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее 
        # самого подсчета динамики
        for prev_mask in range(2 ** m):
            # Раньше мы здесь проверяли, что количество вариантов в этой ветке не 0, сейчас нужно
            # проверить, что эта ветка ведет к максимальному покрытию
            if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \
                    (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and \
                    dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
                mask = prev_mask
                result[prev_k][prev_j] = num
                result[prev_k + 1][prev_j] = num
                num += 1
                break
            elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and \
                    prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
                mask = prev_mask
                result[prev_k][prev_j] = num
                result[prev_k][prev_j + 1] = num
                num += 1
                break
            elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \
                    (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:
                mask = prev_mask
                break
            elif ((1 << prev_j) & prev_mask) == 0 and tiling[prev_k][prev_j] == '.' and \
                    (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] + 1 == dp[k][j][mask]:
                mask = prev_mask
                break

        j = prev_j
        k = prev_k

    return result

И попробуем фигурку из заголовка

tiling_custom=[
    '...####',
    '....###',
    '......#',
    '#.#....',
    '#......',
    '##.....',
    '###...#',
]
filling = cover_maximum_possible(tiling_custom)
draw_filling(filling)

Опа! Не получилось, в общем так и должно было быть. Прежде, чем пойти дальше пару слов о сложности алгоритмов. Всего фигурок $n\times m\times 2^m$ , все переходы константные, отсюда асимптотика $\mathcal{O}(nm2^m)$ , которая может быть улучшена до $\mathcal{O}(nm2^{\min(n, m)})$ если добавить транспонирование в случае, если $inline$ . Построение конкретного замощения в приведенных реализациях имеет сложность $\mathcal{O}(nm2^m)$ , но можно сделать так, чтобы было просто $\mathcal{O}(nm)$ , но это банально больше кода.

Замощение с помощью решения задачи о максимальном паросочетании

Возвращаясь к черно-белой раскраске как на шахматной доске можно заметить интересную интерпретацию задачи замощения доминошками. Давайте посмотрим на граф, в котором клетки фигуры — это вершины, ребрами соединены клетки, имеющие общую сторону. Так вот, доминошка в этом графе — это как раз ребро. Если раскрасить граф в шахматном порядке, то внезапно можно обнаружить, что этот граф — двудольный, черные — одна доля, белые — другая. Если переформулировать задачу замощения наибольшего числа клеток в терминах этого графа, то получается, что нужно найти максимальное по размеру множество ребер такое, чтобы вершины являлись концом не более одного ребра. В общем то, это довольно известная задача о максимальном паросочетании. Давайте попробуем её применить для решения этой задачи, тут получится даже с анимацией, приведу базовый алгоритм Куна для нахождения максимального паросочетания.

Реализация алгоритма Куна для паросочетаний на графе доминошек

def check_valid(i, j, n, m, tiling):
    return 0 <= i and i < n and 0 <= j and j < m and tiling[i][j] != '#'

def find_augmenting_path(x, y, n, m, visited, matched, tiling):
    if not check_valid(x, y, n, m, tiling):
        return False
    if (x, y) in visited:
        return False
    visited.add((x, y))

    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if not check_valid(x + dx, y + dy, n, m, tiling):
            continue
        if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):
            matched[(x + dx, y + dy)] = (x, y)
            return True
    return False

def convert_match(matched, tiling, n, m):
    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]
    num = 0
    for x, y in matched:
        _x, _y = matched[(x, y)]
        result[x][y] = num
        result[_x][_y] = num
        num += 1
    return result

def match_with_flow(tiling):
    result_slices = []
    n = len(tiling)
    m = len(tiling[0])

    matched = dict()
    # Для наглядности визуализации
    rows = list(range(n))
    columns = list(range(m))
    random.shuffle(rows)
    random.shuffle(columns)
    result_slices.append(convert_match(matched, tiling, n, m))

    for i in rows:
        for j in columns:
            if (i + j) % 2 == 1:
                continue
            visited = set()
            if find_augmenting_path(i, j, n, m, visited, matched, tiling):
                result_slices.append(convert_match(matched, tiling, n, m))

    return result_slices

Здесь даже получается проанимировать процесс

sequencial_match = match_with_flow(tiling_custom)

Суть алгоритма Куна (да и любого другого алгоритм для нахождения максимального паросочетания) заключается в нахождении "аугментирующих путей". В терминах доминошек это цепочка из доминошек, у которой рядом с доминошками на концах есть по свободной клетке, такие цепочки можно заменить на цепочки большей длины, охватывающие те же клетки и заполняя две свободные клетки рядом с концами цепочки. Более того, основное утверждение, на котором работают все алгоритмы нахождения максимального паросочетания, заключается в том, что если такой цепочки не удается найти, то значит большего замощения нам не получить.

UPD. Для последнего примера простое обоснование на основе черно-белой раскраски не работает. Насколько мне известно, есть два общих критерия для существования полного замощения:

Теорема Холла (теорема о свадьбах)
Проверка условий этой теоремы вычислительно сложнее, чем построить максимальное паросочетание.
Условие высоты Тёрстона про это я мало что знаю

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

Бонус! Раскраска планарного графа в 5 цветов.

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

Покраска доминошек в 5 цветов

def color_5(filling):
    result = [[i for i in row] for row in filling]
    # Строим граф
    domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]
    domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]
    degree = [0 for i in range(max(map(max, filling)) + 1)]

    n = len(filling)
    m = len(filling[0])

    for i, row in enumerate(filling):
        for j, num in enumerate(row):
            if num >= 0:
                domino_tiles[num].append((i, j))

    for i, tiles in enumerate(domino_tiles):
        for x, y in tiles:
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                a, b = x + dx, y + dy
                if 0 <= a and a < n and 0 <= b and b < m and filling[a][b] >= 0 and filling[a][b] != i \
                        and filling[a][b] not in domino_neighbours[i]:
                    domino_neighbours[i].add(filling[a][b])
                    degree[i] += 1

    # Первым делом нужно найти такой порядок вершин, все вершины имели не больше 5 соседей среди
    # предыдущих. Такой существует в силу того, что граф планарный, а найти его эффективнее всего
    # по очереди находя вершину наименьшей степени и удаляя её из графа, так мы получаем обратный порядок
    active_degrees = [set() for i in range(max(degree) + 1)]
    for i, deg in enumerate(degree):
        active_degrees[deg].add(i)

    reversed_order = []

    for step in range(len(domino_tiles)):
        min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) > 0])
        domino = active_degrees[min_degree].pop()

        reversed_order.append(domino)
        for other in domino_neighbours[domino]:
            if other in active_degrees[degree[other]]:
                active_degrees[degree[other]].remove(other)
                degree[other] -= 1
                active_degrees[degree[other]].add(other)                

    # Теперь перебираем в обратном порядке и либо красим в еще не занятый цвет,
    # если есть свободный из 5 цветов, иначе находим цепочку из чередующихся цветов,
    # которые могут быть перекрашены. Такая найдется в силу планарности
    colors = [-1 for domino in domino_tiles]
    slices = [draw_filling(result)]
    for domino in reversed(reversed_order):
        used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]

        domino_color = len(used_colors)
        for i, color in enumerate(sorted(set(used_colors))):
            if i != color:
                domino_color = i
                break

        if domino_color < 5:
            colors[domino] = domino_color
            for x, y in domino_tiles[domino]:
                result[x][y] = domino_color

            slices.append(draw_filling(result))        
            continue

        # Начиная отсюда код я не тестировал, не нашел примера        
        c = 0
        other = [other for other in domino_neighbours[domino] if colors[other] == c]
        visited = set([other])
        q = Queue()
        q.put(other)
        domino_was_reached = False
        while not q.empty():
            cur = q.get()
            for other in domino_neighbours[cur]:
                if other == domino:
                    domino_was_reached = True
                    break
                if color[other] == c or color[other] == c + 1 and other not in visited:
                    visited.add(other)
                    q.put(other)

        if not domino_was_reached:
            for other in visited:
                color[other] = color[other] ^ 1
                for x, y in domino_tiles[other]:
                    result[x][y] = color[other]
            color[domino] = c
            for x, y in domino_tiles[domino]:
                result[x][y] = c

            slices.append(draw_filling(result))
            continue

        # Проделываем тоже самое для 2 и 3.
        c = 2
        other = [other for other in domino_neighbours[domino] if colors[other] == c]
        visited = set([other])
        q = Queue()
        q.put(other)
        domino_was_reached = False
        while not q.empty():
            cur = q.get()
            for other in domino_neighbours[cur]:
                if other == domino:
                    domino_was_reached = True
                    break
                if color[other] == c or color[other] == c + 1 and other not in visited:
                    visited.add(other)
                    q.put(other)
        for other in visited:
            color[other] = color[other] ^ 1
            for x, y in domino_tiles[other]:
                result[x][y] = color[other]
        color[domino] = c
        for x, y in domino_tiles[domino]:
            result[x][y] = c
        slices.append(draw_filling(result))

    return result, slices

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

Ну и наконец попробуем один из примеров, который был чуть раньше

Tags:

Hubs: