Петоріс#3625
Ви граєте в головоломку під назвою petoris. Гра відбувається на дошці, поділеній на квадратні клітинки, і квадратних плитках, кожна з яких підходить для однієї клітинки. На кожному кроці гри у вас є дошка, частково заповнена плитками. У вас також є блок, що складається з кількох плиток. Ви повинні розмістити цей блок десь на дошці або відкинути його, дотримуючись наступних обмежень на розміщення:
блок можна повертати, але не можна ділити чи перевертати;
жодна з плиток блоку не може стикатися з будь-якими плитками, що вже є на дошці; та
всі плитки блоку повинні бути розміщені всередині дошки.
Ваше завдання — написати програму, яка знайде максимальний бал, який ви можете заробити на цьому кроці. Тут бал — це кількість горизонтальних рядків, повністю заповнених плитками після розміщення блоку, або у разі відкидання.
Перша строка введення — це , кількість наборів даних. Далі йдуть наборів даних. Кожен набір даних складається з рядків, що описують блок і дошку. Кожен опис (як для блоку, так і для дошки) починається з рядка, що містить два цілі числа і , вертикальний і горизонтальний розмір. Потім слідують рядків, кожен з символами, де '#' представляє плитку, а '.' — порожнє місце. Ви можете припустити, що 0 < H \leq 64 і 0 < W \leq 64. Кожен блок складається з однієї або більше плиток, всі з яких з'єднані. Кожна дошка містить нуль або більше плиток і не має горизонтального рядка, повністю заповненого плитками на початковому етапі.
Для кожного набору даних виведіть в одному рядку максимальний можливий бал.
Приклад 1