Петорис
Вы играете в головоломку под названием petoris. Игра проходит на доске, разделенной на квадратные клетки, и квадратных плитках, каждая из которых занимает одну клетку. На каждом этапе игры у вас есть доска, частично заполненная плитками, и блок, состоящий из нескольких плиток. Ваша задача — разместить этот блок на доске или отказаться от него, соблюдая следующие правила:
блок можно поворачивать, но нельзя делить или переворачивать;
плитки блока не должны соприкасаться с плитками, уже находящимися на доске;
все плитки блока должны быть размещены в пределах доски.
Ваша цель — написать программу, которая определит максимальное количество очков, которые можно заработать на этом этапе. Количество очков определяется как количество полностью заполненных горизонтальных рядов плиток после размещения блока, или −1, если блок был отброшен.
Входные данные
Первая строка входных данных содержит число N, обозначающее количество наборов данных. Далее следуют N наборов данных. Каждый набор данных включает описание блока и доски. Описание начинается с двух целых чисел H и W, обозначающих вертикальное и горизонтальное измерения соответственно. Затем следуют H строк, каждая из которых содержит W символов: '#' обозначает плитку, а '.' — пустое место. Гарантируется, что 0 < H ≤ 64 и 0 < W ≤ 64. Каждый блок состоит из одной или нескольких соединенных плиток. Каждая доска может содержать ноль или более плиток и не имеет полностью заполненных горизонтальных рядов в начальном состоянии.
Выходные данные
Для каждого набора данных выведите в отдельной строке максимальное возможное количество очков.