Java: непрерывная область в многомерном массиве, используемая для реализации латинского квадрата

Question

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

Потенциальный Латинский квадрат и местоположение региона считываются одновременно.Регион [0,1][0,2][1,1][1,2] будет действительным регионом, потому что он является смежным;[0,0][0,2][1,1][1,2] не будет смежным или действительным, потому что [0,0] не может быть достигнуто.Как бы я сказал, если они смежные?

Answer 1

Ваш вопрос предполагает как минимум две простые проверки для разных вещей.Если вы просто хотите проверить, что каждая точка достижима из любой другой точки, вы можете рассматривать точки как узлы в сети, где [x, y] связан с [x - 1, y], [x + 1, y], [x, y - 1] и [x, y + 1].Вы можете найти все узлы, достижимые из данного начального узла, используя поиск в глубину.Сделайте такой поиск с произвольного начального узла.Если вы посещаете все узлы, то выбранный регион является смежным.Я полагаю, что это просто заливка, происходящая из другого фона.

Для латинского квадрата подходит ли любая смежная область, или вам нужен прямоугольник с выравниванием по оси?Например, если в вашем соседнем регионе всего три точки, это нормально?Если вы хотите проверить прямоугольник, выровненный по оси, определите максимальное и минимальное значения x и y в наборе, а затем убедитесь, что у вас есть каждая комбинация [a, b], где Xmin <= a <= Xmax иYmin <= b <= Ymax. </p>

Answer 2

Разумным подходом к решению этой проблемы является алгоритм заливки .

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