Условие:
Вы QA-инженер в крупной компании. Она недавно выпустила новый будущий хит — тетрис. Вам положено протестировать его.
Поле тетриса представляет собой поле n * m, на котором расположены фигуры из тетриса, представленные на картинке ниже (фигуры могут быть повернуты на 90, 180 или 270 градусов, но не могут быть зеркально отражены). Каждой клетке, занятой фигурой, соответствует маленькая буква латинского алфавита. Известно, что каждой фигуре соответствуют одинаковые буквы (но двум фигурам одинакового типа могут соответствовать разные буквы). Также гарантируется, что нет двух соседних по клеткам фигур, которым соответствует одинаковая буква.
Вам требуется для каждого типа фигур определить, сколько фигур данного типа расположено на поле.
Формат входных данных
В первой строке заданы два числа n, m (1 <= n, m <= 10) — размеры поля.
В следующих n строках идут описания строк поля. Буквы соответствуют частям фигур, а символ . соответствует тому, что в клетке не лежит никакая из частей фигуры.
Формат выходных данных
Выведите 5 строк, где в i-й строке нужно вывести количество фигур типа i, расположенных на поле.
Тест-кейс для данной задачи
Ввод
4 4
bb.a
.bba
.cca
cc.a
Вывод
0
1
1
1
0
Решение:
Для решения задачи, нам нужно определить количество фигур тетриса, представленных на поле, и классифицировать их по типам. Давайте разберем шаги, которые мы будем выполнять.
Шаг 1: Понимание входных данных
Мы имеем поле размеромn x m, где n и m — это размеры поля (в данном случае 4x4). Каждая фигура представлена буквой латинского алфавита, а пустые клетки обозначены символом ..Шаг 2: Определение типов фигур
В тетрисе есть 5 основных типов фигур:1. I (линейная)
2. O (квадратная)
3. T (Т-образная)
4. J (обратная L-образная)
5. L (L-образная)
Шаг 3: Считывание данных
Считываем размеры поля и само поле. Ввод будет выглядеть следующим образом:
4 4
bb.a
.bba
.cca
cc.a
Шаг 4: Поиск фигур
Мы будем использовать алгоритм поиска в глубину (DFS) для поиска и классификации фигур. Мы будем отмечать уже посещенные клетки, чтобы не считать одну и ту же фигуру несколько раз.Шаг 5: Классификация фигур
Каждый раз, когда мы находим новую фигуру, мы будем определять ее тип, основываясь на ее форме. Для этого мы можем использовать координаты частей фигуры, чтобы понять, к какому типу она относится.Шаг 6: Реализация
Теперь давайте реализуем алгоритм:После выполнения кода, мы получим следующий вывод: Таким образом, мы успешно определили количество фигур каждого типа на поле.