Java: непрерывная область в многомерном массиве, используемая для реализации латинского квадрата
Я пишу программу, которая читает на потенциальном латинском квадрате и сообщает, является ли он действительным латинским квадратом или нет. Сейчас я пытаюсь сказать, является ли выбранный регион смежным или нет.
Потенциальная Латинская площадь и местоположение региона читаются одновременно. Область [0,1][0,2][1,1][1,2] будет действительным регионом, потому что он является смежным; [0,0][0,2][1,1][1,2] не будет смежным или действительным, потому что [0,0] не может быть достигнуто Как бы я сказал, если они смежные?
2 ответа
Разумный подход к этой проблеме - алгоритм заполнения потока.
По сути, начните с любой точки вашего региона и создайте набор местоположений в вашем регионе, которые связаны с начальной точкой, отметив всех своих соседей в регионе, а затем отметив всех своих соседей в регионе, которые еще не отмечены, Когда нет ничего нового для отметки, вы нашли максимальную непрерывную область, содержащую вашу начальную точку. Если это не весь регион, регион не является смежным.
Ваш вопрос предлагает как минимум две простые проверки, для разных вещей. Если вы просто хотите проверить, что каждая точка достижима из любой другой точки, вы можете рассматривать точки как узлы в сети, где [x,y] связан с [x - 1, y], [x + 1, y], [x, y - 1] и [x, y + 1]. Вы можете найти все узлы, достижимые из данного начального узла, используя поиск в глубину. Сделайте такой поиск с произвольного начального узла. Если вы посещаете все узлы, то выбранный регион является смежным. Я предполагаю, что это просто заливка из другого фона.
Для латинского квадрата все смежные области в порядке, или вам нужен прямоугольник с осями? Например, если в вашем смежном регионе всего три точки, это нормально? Если вы хотите проверить прямоугольник, выровненный по оси, определите максимальное и минимальное значения x и y в наборе, а затем убедитесь, что у вас есть каждая комбинация [a, b], где Xmin <= a <= Xmax и Ymin <= b <= Ymax.