Как правильно алгоритмически решить эту задачу?

Question

Мне нужно от каждой точки провести вертикальные и горизонтальные линии и найти пересечения с теми прямыми, которые испускают другие точки. Как правильно это сделать? На скрине символьный спискок Python. У меня из идей разве что от каждой точки сначально горизонтально, потом вертикально заполнять, например, "#" и если на данном месте есть "#" пометить эту точку другим символом, например "&". Ну это решение прям в лоб и крайне не быстрое. Есть у кого предложение поинтереснее?

Answer 1

поскольку прямые параллельно-перпендикулярные (относительно сетки), то почему бы не сделать просто:

проходим по всем точкам из которых надо вывести прямые - p1 (N точек)
для каждой точки проходим по всем точкам кроме текущей - p2 (N - 1 точек)
отмечаем точки в координатах [p1.x][p2.y] (N - 1 точек) и [p1.y][p2.x] (N - 1 точек)

пример такого кода:

field = list(list())

# собрать список полей с объектами
objects = []

for i in range(len(field)):
    for j in range(len(field[i])):
        if field[i][j] == 'x':
            objects.append((i, j))


# расставить точки
for i in range(len(objects)):

    x1, y1 = objects[i]

    for j in range(len(objects)):
        
        # не рассматривать взаимодействие объекта самого с собой
        if i == j:
            continue

        x2, y2 = objects[j]

        # если поле пустое - поставить точку
        if field[x1][y2] == ' ':
            field[x1][y2] = '.'

        if field[x2][y1] == ' ':
            field[x2][y1] = '.'

Answer 2

Лучшим решением, наверное, будет для каждого символа запоминать две прямые, заданные в виде y = kx + b. За координаты стоит принять индексы массива. Пробегаясь по нему, строим дикт: ключ - это буква, а значение - массив вида [ [k1, b1], [k2, b2]]. После этого достаточно найти точки пересечения прямых, что совсем нетрудно. Однако остаётся вопрос насчёт совпадающих прямых: a и f в приложенном вами сриншоте дадут такой результат. Сложность алгоритма получается O(n^2), где n - количество букв в матрице.

БЛОГ НА HUSL

Как правильно алгоритмически решить эту задачу?

Ответы (2 шт):