Постановка проблемы:
Проблема Аполлон играет в игру с участием полиомино. Полимино - это форма, образованная соединением одного или нескольких квадратов край к краю, чтобы сформировать единую соединенную форму. Игра включает объединение N полимино в один прямоугольник angular без отверстий. Каждое полимино помечено уникальным символом от A до Z.
Apollo завершил игру и создал прямоугольную angular стену, содержащую R строк и C столбцов. Он сделал снимок и отправил его своей подруге Селене. Селене нравятся изображения стен, но они нравятся ей еще больше, если это устойчивые стены. Стена является стабильной, если ее можно создать, добавляя полиомино по одному к стене, чтобы каждый полиомино всегда поддерживался. Полимино поддерживается, если каждый из его квадратов либо стоит на земле, либо имеет другой квадрат под ним. порядок, в котором он добавил полимино.
Входные данные В первой строке входных данных указано количество тестовых примеров, далее следуют T-тестовые примеры. Каждый тестовый пример начинается со строки, содержащей два целых числа R и C. Затем следуют R-линии, описывающие стену сверху вниз. Каждая строка содержит строку C заглавных символов от A до Z, описывающих эту строку стены.
Выходные данные Для каждого тестового примера выведите одну строку, содержащую Case #x: y, где x - тест номер регистра (начиная с 1) и y - это строка из N символов верхнего регистра, описывающая порядок, в котором он их построил. Если таких заказов несколько, выведите любой из них. Если стена нестабильна, выведите вместо нее -1.
Ограничения Ограничение по времени: 20 секунд на тестовый набор. Ограничение памяти: 1 ГБ. 1 ≤ T ≤ 100. 1 ≤ R ≤ 30. 1 ≤ C ≤ 30. Никакие два полимино не будут обозначены одной и той же буквой. Ввод гарантированно действителен в соответствии с правилами, описанными в заявлении.
Тестовый набор 1 1 ≤ N ≤ 5.
Тестовый набор 2 1 ≤ N ≤ 26.
Пример
Вход
Выход
4 4 6 ZOAAMM ZOAOMM ZOOOOM ZZZZOM 4 4 XXOO XFFO XFXO XXXO 5 3 XXX XPX XXX XJX XXX 3 10 AAABBCCDDE AABBCCDDEE AABBCCDDEE
Случай № 1: ZOAM Случай № 2: -1 Случай № 3: -1 Случай № 4: EDCBA
В примере случая № 1 обратите внимание, что ZOMA - еще один возможный ответ.
В примере № 2 и № 3 стена нестабильна, поэтому ответ - -1.
В примере № 4 единственный возможный ответ - EDCBA.
Предварительная проверка синтаксиса Показать тестовый ввод
Мой код:
class Case:
def __init__(self, arr):
self.arr = arr
def solve(self):
n = len(self.arr)
if n == 1:
return ''.join(self.arr[0])
m = len(self.arr[0])
dep = {}
used = set() # to save letters already used
res = []
for i in range(n-1):
for j in range(m):
# each letter depends on the letter below it
if self.arr[i][j] not in dep:
dep[self.arr[i][j]] = set()
# only add dependency besides itself
if self.arr[i+1][j] != self.arr[i][j]:
dep[self.arr[i][j]].add(self.arr[i+1][j])
for j in range(m):
if self.arr[n-1][j] not in dep:
dep[self.arr[n-1][j]] = set()
# always find and desert the letters with all dependencies met
while len(dep) > 0:
# count how many letters are used in this round, if none is used, return -1
count = 0
next_dep = {}
for letter in dep:
if len(dep[letter]) == 0:
used.add(letter)
count += 1
res.append(letter)
else:
all_used = True
for neigh in dep[letter]:
if neigh not in used:
all_used = False
break
if all_used:
used.add(letter)
count += 1
res.append(letter)
else:
next_dep[letter] = dep[letter]
dep = next_dep
if count == 0:
return -1
if count == 0:
return -1
return ''.join(res)
t = int(input())
for i in range(1, t + 1):
R, C = [int(j) for j in input().split()]
arr = []
for j in range(R):
arr.append([c for c in input()])
case = Case(arr)
print("Case #{}: {}".format(i,case.solve()))
Мой код успешно проходит все примеры примеров, которые я могу придумать, но по-прежнему получает WA при отправке. Может ли кто-нибудь заметить, что не так с моим решением? Спасибо