Найдите те же шаблоны в 2D массивах

Question

В одном интервью мне дали несколько двумерных массивов и попросили идентифицировать и подсчитать одинаковые образцы значений, встречающихся внутри каждого из этих массивов.

Шаблоны могут быть любой формы. Они могут быть квадратами, крестами, могут иметь любую повторяющуюся форму.

Графически данные выглядят примерно так:

ArrayOne
[0][1][1][0]
[0][1][1][0]

ArrayTwo
[1][1][0][0]
[0][1][0][0]
[0][1][0][0]

ArrayThree
[0][1]1][0]
[0][1][1][0]
[0][0][0][0]
[0][0][0][0]

И как результат можно ожидать увидеть:

ArrayOne ArrayThree - "Two occurrencies"
ArrayTwo ArrayTwo - "One occurency"

В нынешнем виде я не вижу, как мы можем повторять такие массивы, чтобы извлекать их шаблоны. Конечно, мы могли бы посчитать количество единиц в каждом массиве, но практически это бесполезно и не даст ответа на вопрос.

Сильно бы оценил конструктивный совет о том, как этого добиться в Java или любом другомдругой широко используемый объектно-ориентированный язык.

РЕДАКТИРОВАТЬ: содержимое массива были обновлены, чтобы устранить путаницу, которая присутствовала в исходном посте

Answer 1

Они могут быть квадратами, крестами

Мне кажется, что определение «шаблона» - это группа связанных ненулевых ячеек. Вопрос о том, считаются ли диагонали соединенными, остается спорным, но для квадратов и крестов они не обязательны.

Теперь соберите все такие шаблоны в Set двумерных массивов. Например, см. Найдите количество островов , чтобы узнать, как найти шаблоны.

Пример:

1 1 1 1 0
0 1 0 0 0
1 1 0 1 1
1 0 0 1 0

Содержит 2 шаблона:

1 1 1 1     1 1
0 1 0 0     1 0
1 1 0 0
1 0 0 0

Создайте Set шаблонов для каждого входного массива, затем посмотрите, имеют ли наборы общие шаблоны.

Или, если у вас много входных массивов, создайте Map<Pattern, List<String>>, где Pattern - это перенос класса2D-массив и реализующий equals() и hashCode(), а String - имя входного массива.

Answer 2

Это типичный вопрос любого начала курса программирования.

Квадратные и перекрестные узоры можно распознать с помощью вложенных циклов.

Начать сканирование матрицы с индекса 0,0. Сначала [1] вхождения сохраняют индексы как начальные индексы и перемещаются по остальной части матрицы в нужном направлении (следите за тем, чтобы не превышать максимальный размер матрицы).

Типичный шаблон распознавания квадрата / прямоугольника

x---->|
^     |
|     v
|<-----

Вы также можете проверить, заполнено ли оно. Аналогично, для перекрестного шаблона идите по прямой, увеличивая индексы как строк, так и столбцов.