Блог

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

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

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

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

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

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