Поместить все фигуры в матрицу

@Khimer · Регистрация: 04.05.2020

Студворк — интернет-сервис помощи студентам

Весь код внизу.

У меня есть определенные фигуры, определенного цвета.

Например, фигура цветом 6 имеет форму квадрата 2х2

Python
1
2
3
4
5
[6, 6, 0, 0, 0]
[6, 6, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

Фигура цветом 5 имеет форму

Python
1
2
3
4
5
[5, 5, 0, 0, 0]
[5, 5, 5, 0, 0]
[5, 5, 5, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

(все остальные фигуры увидите если запустите код).

На самом деле у меня txt файл

Python
1
2
3
4
5
6
7
8
5
5
6 0 4 0 5 -1 5 -1 4
5 4 2 4 1 4 0 3 1 3 2 3 0 2 1 2 0
2 6 4 7 4 7 3
3 -2 9 -3 9
4 7 10 8 10 8 11 9 10 6 10 5 10
1 4 14 4 13

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def readStones(filename):
    stones = []
    f = open(filename,"r")
    numRows = int(f.readline().strip())  #1 ряд файла
    numCols = int(f.readline().strip())  #2 ряд файла
    for line in f:
        numbers = list(map(int, line.strip().split()))  #все числа после этих двух рядов
        color = numbers[0]                              #первый столбец это цвета
        coords = numbers[1:]                            #r1 c1 ... rn cn
        cells = []                                      #[r1,c1 ... rn,cn] = [[r1,c1],...,[rn,cn]]
        for i in range(len(coords)//2):
            cells.append( [ coords[2*i+0], coords[2*i+1] ] )
        stones.append( [ color, cells ] )
    f.close()
    return numRows, numCols, stones;
 
 
def shape_of_stones(numRows, numCols, stones, n):
    '''find out the shape of the stones '''
    matrix_for_shape = [0] * numRows
    for k in range(numRows):
        matrix_for_shape[k] = [0] * numCols
    rows = [] 
    cols = []
    for cellindex in range(len(stones[n][1])):
        row, col = stones[n][1][cellindex]
        rows.append(row)
        cols.append(col)
    for cell in range(len(stones[n][1])):
        r, c = stones[n][1][cell]
        i = stones[n][0]
        matrix_for_shape[r - min(rows)][c - min(cols)] = i
    print(*matrix_for_shape, sep='\n')
 
    def main():
    M,N, stones = readStones("stones.txt")
 
    #информация о камнеstones[n]
    #его цвет stones[n][0], его координаты stones[n][1]    
 
    for n in range(len(stones)):
        shape_of_stones(M, N, stones, n)
        print('--------'*2)
main()

Не могу придумать рекурсивную функцию, которая бы поместила все фигуры.

Вот как можно собрать все эти фигуры

Python
1
2
3
4
5
[4, 5, 5, 1, 1]
[4, 5, 5, 5, 3]
[4, 5, 5, 5, 3]
[4, 4, 2, 6, 6]
[4, 2, 2, 6, 6]

@idealist · 01.12.2021, 20:48

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
class Shape:
    def __init__(self, s):
        s = s.split()
        self.color = s[0]                                                   #Цвет
        self.cells_list = []
 
        for ind in range(1, len(s), 2):
            i = int(s[ind])
            j = int(s[ind+1])
            self.cells_list.append([i,j])                                   #Список клеток
            
        self.cells_list.sort()
 
        self.up_left_cell = self.cells_list[0].copy()                       #Верхняя левая клетка
        
        for cell in self.cells_list:
            self.up_left_cell[0] = min(cell[0], self.up_left_cell[0])
            self.up_left_cell[1] = min(cell[1], self.up_left_cell[1])
 
        #Сдвигаем фигуру так, чтобы верхняя левая клетка стала равной (0,0)
        new_cells_list = []
        for cell in self.cells_list:
            i_new = cell[0] - self.up_left_cell[0]
            j_new = cell[1] - self.up_left_cell[1]
            new_cells_list.append([i_new, j_new])
 
        self.cells_list = new_cells_list.copy()
        self.up_left_cell = [0, 0]
 
        lower_right_cell = self.cells_list[0].copy()                        #Нижняя правая клетка
        for cell in self.cells_list:
            lower_right_cell[0] = max(cell[0], lower_right_cell[0])
            lower_right_cell[1] = max(cell[1], lower_right_cell[1])
 
        self.height = lower_right_cell[0] - self.up_left_cell[0] + 1        #Высота фигуры
        self.width  = lower_right_cell[1] - self.up_left_cell[1] + 1        #Ширина фигуры
 
        self.square = len(self.cells_list)                                  #Площадь фигуры
    #===========================================================================
    #Перегрузка метода сортировки
    def __lt__(self, other):
        return self.square < other.square
#===============================================================================
def get_shape_cells(shape, shape_pos):
    res_cells = set()
 
    for cell in shape.cells_list:
        i_new = cell[0] + shape_pos[0]
        j_new = cell[1] + shape_pos[1]
        res_cells.add((i_new, j_new))
    return res_cells
#===============================================================================
def good_insert_shape(matr_height, matr_width, occupied_matr_cells, shapes_list,\
        shapes_positions, ind_cur):
    shape_cur = shapes_list[ind_cur]
    shape_height = shape_cur.height
    shape_width  = shape_cur.width
 
    for i in range(matr_height - shape_height + 1):
        for j in range(matr_width - shape_width + 1):
            shape_cells_cur = get_shape_cells(shape_cur, [i, j])
            if len(shape_cells_cur & occupied_matr_cells) == 0:
                shapes_positions[ind_cur] = (i,j)
                occupied_matr_cells |= shape_cells_cur
                return True
    return False
#===============================================================================
def good_move_shape(matr_height, matr_width, occupied_matr_cells, shapes_list,\
        shapes_positions, ind_cur):
    shape_cur = shapes_list[ind_cur]
    shape_height = shape_cur.height
    shape_width  = shape_cur.width
            
    shape_pos           =  shapes_positions[ind_cur]
    occupied_matr_cells -= get_shape_cells(shape_cur, shape_pos)
 
    for i in range(shape_pos[0], matr_height - shape_height + 1):
        for j in range(matr_width - shape_width + 1):
            if i > shape_pos[0] or j > shape_pos[1]:
                shape_cells_cur = get_shape_cells(shape_cur, [i, j])
                if len(shape_cells_cur & occupied_matr_cells) == 0:
                    shapes_positions[ind_cur] = (i,j)
                    occupied_matr_cells |= shape_cells_cur
                    return True
    return False
#===============================================================================
def print_variant(matr_height, matr_width, shapes_list, shapes_positions):
    s = ''
    for i in range(len(shapes_list)):
        s += shapes_list[i].color + '\t'
    print('Цвета фигур:\t', s)
 
    print('Позиции фигур: ','\t'.join(map(str, shapes_positions)))
    print()
#===============================================================================
def count_variants_of_placement(matr_height, matr_width, shapes_list):
    variants_counter       = 0
    EMPTY_POSITION         = None
    START_SHAPES_POSITIONS = [EMPTY_POSITION] * len(shapes_list)
    shapes_positions       = START_SHAPES_POSITIONS
    occupied_matr_cells    = set()
    ind_cur                = 0
    insert_res             = False
 
    while True:
        if shapes_positions[ind_cur] == EMPTY_POSITION:
            insert_res = good_insert_shape(matr_height, matr_width, occupied_matr_cells,\
                shapes_list, shapes_positions, ind_cur)
        else:
            insert_res = good_move_shape(matr_height, matr_width, occupied_matr_cells,\
                shapes_list, shapes_positions, ind_cur)
 
        if insert_res:
            if ind_cur == len(shapes_list) - 1:
                variants_counter += 1
                print_variant(matr_height, matr_width, shapes_list, shapes_positions)
            else:
                ind_cur += 1
        else:
            shapes_positions[ind_cur] = EMPTY_POSITION
            if ind_cur == 0:
                return variants_counter
            else:
                ind_cur -= 1
#===============================================================================
def main():
    matr_height = int(input('Высота матрицы = '))
    matr_width  = int(input('Ширина матрицы = '))
    
    shapes_list = []
    shapes_list.append( Shape('6 0 4 0 5 -1 5 -1 4'))
    shapes_list.append( Shape('5 4 2 4 1 4 0 3 1 3 2 3 0 2 1 2 0'))
    shapes_list.append( Shape('2 6 4 7 4 7 3'))
    shapes_list.append( Shape('3 -2 9 -3 9'))
    shapes_list.append( Shape('4 7 10 8 10 8 11 9 10 6 10 5 10'))
    shapes_list.append( Shape('1 4 14 4 13'))
    shapes_list.sort(reverse = True)
 
    var_counter = count_variants_of_placement(matr_height, matr_width, shapes_list)
    print('В матрице ', matr_height,'X', matr_width, 'вариантов расстановки', var_counter)
#===============================================================================
main()

@Khimer · 01.12.2021, 21:10 **[ТС]**

idealist, спасибо, но уже решил попроще

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def readStones(filename):
    stones = {} 
    with open(filename, "r") as f:
        numRows = int(f.readline().strip())
        numCols = int(f.readline().strip())
        for line in f:
            numbers = list(map(int, line.strip().split()))
            color = numbers[0]
            coords = numbers[1:]
            cells = [coords[i:i + 2] for i in range(0, len(coords), 2)]
            stones[color] = cells
    return numRows, numCols, stones;
 
 
def shape_of_stones(coords, color=None):
    rows, cols = zip(*coords)
    min_row, max_row = min(rows), max(rows)
    min_col, max_col = min(cols), max(cols)
    height = max_row - min_row + 1
    width = max_col - min_col + 1
    norm_rows = map(lambda row: row - min_row, rows)
    norm_cols = map(lambda col: col - min_col, cols)
    norm_coords = list(zip(norm_rows, norm_cols))
    if color is not None:
        matrix_for_shape = [[0]*width for _ in range(height)]
        for row, col in norm_coords:
            matrix_for_shape[row][col] = color
    return (width, height, norm_coords)
 
def place_stone(stones, n_rows, n_cols, pole=None):
    if not stones:
        return pole
    if pole is None: 
        pole = [[0]*n_cols for _ in range(n_rows)]
    for color in stones:
        rest_stones = stones.copy() 
        width, height, coords = rest_stones.pop(color)
        print(*pole, sep = '\n')
        print('-'*10)
        for row in range(n_rows - height + 1):
            for col in range(n_cols - width + 1):
                if all(pole[row+r][col+c] == 0 for r, c in coords):
                    new_pole = copy.deepcopy(pole)
                    for r, c in coords:
                        new_pole[row+r][col+c] = color
                    result = place_stone(rest_stones, n_rows, n_cols, new_pole)
                    if result:
                        return result
 
 
 
def main():
    M,N, stones = readStones("stones.txt")
 
 
 
    for color in stones:
        stones[color] = shape_of_stones(stones[color], color)
 
    stones = {k: v for k, v in sorted(stones.items(), key=lambda item: (item[1][0]*item[1][1], len(item[1][-1])), reverse=True)}
    result = place_stone(stones, M, N)
    if result:
       print(result)
 
    else:
        print('Error')
 
main()

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

Поместить все фигуры в матрицу

Решение