Напиши код

Ниже даю подробное решение и рабочий код на Python. Суть: - Стена заполняется кирпичами размером 1×2, но по рядам чередуется сдвиг (как в обычном кирпичном кле́йку): в чётных рядах начинаем с левого края двумя клетками, в нечётных — сначала ставим одно-клеточный половинчатый кирпич в начале ряда, затем кладём 2-клеточные кирпичи подряд; в концах ряда могут быть половинки кирпичей. - Строим граф, где вершины — кирпичи, а ребра — общие стороны между двумя разными кирпичами. - Раскрашиваем граф минимальным количеством цветов (цвета кодируются цифрами 1,2,3,...). Пробуем раскраску на 2 цвета, затем на 3, затем на 4 (графы на плоскости таковы, что 4 цвета достаточно, поэтому сверху получится). - Выводим по клеткам модуля окрашивания соответствующий цвет кирпича. Пояснения по алгоритму: - Формируем раскладку кирпичей по строкам с чередованием. Каждую клетку помечаем идентификатором кирпича. - Строим соседей для каждого кирпича через чтение соседних клеток в сетке. - Реализуем backtracking-раскраску с упорядочиванием вершин по убыванию степени (чтобы быстрее сузить варианты). - Выбираем минимальное количество цветов k, на которое удаётся раскрасить граф (попробуем 2, затем 3, затем 4). Код (Python): ```python import sys def build_wall(n, m): # grid_brick[r][c] = brick_id grid_brick = [[-1] * m for _ in range(n)] bricks = [] # каждый элемент — список клеток [(r,c), ...] относящийся к одному кирпичу for r in range(n): if r % 2 == 0: # четные ряды: начинаем с левого края c = 0 while c + 1 < m: cells = [(r, c), (r, c + 1)] bricks.append(cells) bid = len(bricks) - 1 for (rr, cc) in cells: grid_brick[rr][cc] = bid c += 2 if m % 2 == 1: # остаток в конце ряда cells = [(r, m - 1)] bricks.append(cells) bid = len(bricks) - 1 grid_brick[r][m - 1] = bid else: # нечётные ряды: в начале ставим половинку, затем 2-клеточные кирпичи if m > 0: cells = [(r, 0)] bricks.append(cells) bid = len(bricks) - 1 grid_brick[r][0] = bid c = 1 while c + 1 < m: cells = [(r, c), (r, c + 1)] bricks.append(cells) bid = len(bricks) - 1 for (rr, cc) in cells: grid_brick[rr][cc] = bid c += 2 if m % 2 == 0: # остаток в конце ряда для чётного m cells = [(r, m - 1)] bricks.append(cells) bid = len(bricks) - 1 grid_brick[r][m - 1] = bid return grid_brick, bricks def build_adjacency(grid_brick, n, m, num_bricks): adj = [set() for _ in range(num_bricks)] dirs = [(1,0), (-1,0), (0,1), (0,-1)] for r in range(n): for c in range(m): a = grid_brick[r][c] for dr, dc in dirs: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < m: b = grid_brick[nr][nc] if b != a: adj[a].add(b) # переведём в список adj_list = [sorted(list(neigh)) for neigh in adj] return adj_list def color_graph_min_colors(adj_list): n = len(adj_list) # Попробуем раскраску для k = 2, 3, 4 for k in range(2, 5): colors = [-1] * n order = sorted(range(n), key=lambda x: len(adj_list[x]), reverse=True) def dfs(idx): if idx == n: return True v = order[idx] # запрещённые цвета соседей forbidden = set() for u in adj_list[v]: if colors[u] != -1: forbidden.add(colors[u]) for col in range(k): if col not in forbidden: colors[v] = col if dfs(idx + 1): return True colors[v] = -1 return False if dfs(0): # вернём цвета как номера 0..k-1 return colors # В теории для планарных графов 4 цвета достаточно, но как резерв # если что, вернём раскраску с 4 цветами (мало вероятно здесь не найдётся) colors = [-1] * n k = 4 order = sorted(range(n), key=lambda x: len(adj_list[x]), reverse=True) def dfs4(idx): if idx == n: return True v = order[idx] forbidden = set() for u in adj_list[v]: if colors[u] != -1: forbidden.add(colors[u]) for col in range(k): if col not in forbidden: colors[v] = col if dfs4(idx + 1): return True colors[v] = -1 return False if dfs4(0): return colors # Ниже на практику не надо return colors def main(): data = sys.stdin.read().strip().split() if not data: return # Формат: две строки (n и m) или две числа в одной строке n = int(data[0]) m = int(data[1]) if len(data) > 1 else 0 if m <= 0: # если вдруг неверный ввод, просто вернёмся return grid_brick, bricks = build_wall(n, m) adj = build_adjacency(grid_brick, n, m, len(bricks)) colors = color_graph_min_colors(adj) # Вывод: n строк по m цифр (цвет кирпича + 1) out = [] for r in range(n): line = [] for c in range(m): bid = grid_brick[r][c] ch = str(colors[bid] + 1) line.append(ch) out.append(''.join(line)) print('\n'.join(out)) if __name__ == "__main__": main() ``` Как работать с этим кодом: - Входные данные: две строки или две числа через пробел — сначала количество рядов n, затем длина ряда m (в клетках). - Выход: n строк, каждая из которых содержит ровно m цифр. Номер цвета кирпича конвертируется в цифру (1, 2, 3, ...). Все клетки одного кирпича имеют одинаковый цвет, соседние кирпичи — разные цвета, количество используемых цветов минимизируется (проверяем 2, затем 3, затем 4). Примечания: - Алгоритм строит один конкретный «кирпичный» рисунок по заданной схеме с чередованием, как и в примере задачи. - Затем ищет минимальное число цветов для раскраски кирпичей с учётом соседства по граням. - Вдобавок учтён случай, когда в рядах возможны половинки кирпичей на концах (вводимый формат поддерживает это через схему заполнения).