У меня есть txt файл, который содержит
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
Первые две строки показывают размер матрицы, в которую надо поместить все фигуры. Первый столбец каждой строки показывает цвет фигуры, а следом идущие числа - это координаты в матрице, такие, что в конце получится фигура.
Например, фигура цветом 6 имеет форму квадрата 2х2
[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 имеет форму
[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]
Вот код, он помещает все фигуры
import copy
filename = 'stones.txt'
with open(filename, 'r') as f:
n_row = int(f.readline().strip())
n_col = int(f.readline().strip())
st = [[*map(int, l.split())] for l in f.readlines()]
def tetr(matr, stones):
if not stones:
return matr
c, *coords = stones.pop()
f = lambda x,y: [i-y for i in x]
row, col = f(coords[::2],min(coords[::2])), f(coords[1::2],min(coords[1::2]))
for x in range(n_row-len(set(row))+1):
for y in range(n_col-len(set(col))+1):
if all(matr[i+x][j+y]==0 for i,j in zip(row,col)):
matr2 = [m.copy() for m in matr]
for i,j in zip(row,col):
matr2[i+x][j+y] = c
res = tetr(matr2, stones.copy())
if res:
return res
return None
field = [[0]*n_col for _ in range(n_row)]
res = tetr(field, st)
print(*res or ['Нет вариантов'], sep = '\n')
Как можно добавить вращения фигур, чтобы возможность заполнить матрицу была выше?
Как вариант, можно попробовать вот эти камни
5
5
1 13 0 13 1 13 -1 13 2
2 3 -2 3 -1 2 -2 2 -3 3 -3 2 -4 4 -1 2 -1 2 0 3 0 4 0 4 -2 4 -3 5 0
3 -3 10 -2 11 -1 10 -3 11 -2 10 -1 11 0 10