sample = (("11", "1 1 2"),
("1111\n1111\n1111\n0100", "2 1 3\n3 1 1\n3 2 1"),
("000101\n001101\n110000\n111111\n001110\n111110",
"1 1 2\n2 1 3\n3 1 1\n2 2 1\n6 1 2"),
("111\n101\n111", "2 1 4"))
class Field:
def flip(self):
self.cells[:] = sorted((x, y) for y, x in self.cells)
self.flipped ^= True
def dismantle(self, cells, flipped):
self.cells, self.flipped = cells, flipped
left, right = cells[0][0], cells[-1][0]
tmp = sorted(y for _, y in cells)
top, bottom = tmp[0], tmp[-1]
h, w = bottom - top + 1, right - left + 1
if w * h == len(cells):
wh = (w, h) if h < w else (h, w)
c = tails.get(wh, 0)
if c:
tails[wh] = c - 1
yield (self,)
tails[wh] = c
for lo, hi in (left, right), (top, bottom):
for i, (x, _) in enumerate(cells):
if lo < x <= hi:
for one in Field().dismantle(cells[:i], self.flipped):
for two in Field().dismantle(cells[i:], self.flipped):
yield [*one, *two]
lo = x
self.flip()
_field, _tails = sample[0]
tails = {}
for s in _tails.splitlines():
w, h, c = map(int, s.split())
if w < h:
w, h = h, w
tails[w, h] = c
for partition in Field().dismantle(
sorted((x, y) for y, s in enumerate(_field.splitlines())
for x, c in enumerate(s) if c == '1'), False):
for f in partition:
if f.flipped:
f.flip()
print(*f.cells)
break
else:
print('не смогла')
Ломается на 3м примере, "бублике". Это чинится, но лень возиться. Односвязные области должна решать всегда (if possible).
