Можно ли создать матрицу смежности из двумерного массива узлов в C ++?

Итак, у меня есть необработанный файл размером 250×200 пикселей, который я прочитал в двумерный массив, например rawFile[250][200] при этом каждый пиксель (каждый индекс массива) выступает в качестве узла, а каждое значение пикселя представляет высоту (например, топографическая карта). Я хочу найти кратчайший путь, используя алгоритм Дейкстры из rawFile[0][0] в rawFile[250][200] при этом стоимость расстояния является абсолютной величиной разницы от node1 в node2 плюс кратчайшее расстояние до текущего посещенного узла. Каждый узел может двигаться в четырех основных направлениях (N, E, S, W), предполагая, что в соответствующем направлении есть соседний узел. Я читал псевдокод и различные реализации, которые все требуют матрицы смежности или списка смежности, который в этом случае будет adjMatrix[50000][50000], Однако я изо всех сил пытаюсь выяснить, как я могу заполнить матрицу смежности только из необработанного файла.

Есть ли у вас какие-либо предложения по решению этой проблемы? Спасибо!

0

Решение

Преобразование изображения в матрицу смежности совершенно не нужно; единственное, что вам нужно, это информация о «соседстве», которая уже присутствует неявно.

Соседи любого пикселя i,j представлены пикселями в (i-1,j), (i+1,j), (i,j-1), (i,j+1) с учетом границ изображения. Вам не нужна матрица для ее кодирования; всякий раз, когда алгоритм говорит смотреть на соседей, просто предоставьте соседние пиксели.

1

Другие решения