Хранение стоимости между узлами

Question

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

Структура данных номеров (названные клетки):

struct Cell 
    { 
     int row; 
     int column; 
     vector<Cell*> neighbors; 
     State state; 
    }; 

строка и столбец являются положение в лабиринте вектора клетки, vector<Cell*> neighbors определяет, с которой клетки эта конкретная ячейка соединена с и состояния держит состояние ячейки (посещение, пустое и т. д.).

То, что я пробовал делать, - это свойство структуры ячеек: vector<int> cost, где каждый элемент этого массива соответствует соседнему элементу.

Например:

0 ###### 
1 # ## 
2 # # # 
3 ###### 

лабиринт [1] [1] имеет в нем соседей вектора:

neighbors[0] = *maze[1][2]; 
neighbors[1] = *maze[2][1]; 

это вектор стоимость сейчас:

cost[0] = 5; 
cost[1] = 10; 

Но путь Это создало много проблем.

То, что я думал, что мне нужно матрица затрат, которая будет соответствовать одному узлу с другим и хранить стоимость в матрице, что-то вроде этого:

0 1 2 
0[0][2][4] 
1[2][0][6] 
2[4][6][0] 

Но для того, чтобы сделать это, как буду я сделать мою матрицу известной, какая ячейка есть? как вместо 0 и 1 я знаю, что это [0] [0] [0] [1] [0] [2] и т. д.

Нужно ли использовать 3D-вектор для чего-то подобного? Если я это сделаю, я бы предпочел избежать этого, так как я неопытен с 3D-векторами.

Answer 1

Не могли бы вы использовать пользовательский объект для своей ссылки в другую комнату? Например:

struct Cell; 

struct CellLink { 
    const Cell *cell; 
    const int weight; 
    .. 
}; 

struct Cell { 
    int row; 
    int column; 
    vector<CellLink> neighbors; 
    State state; 
}; 

Это будет поддерживать стоимость и сотовую связь без каких-либо проблем. Единственным недостатком является то, что вы будете хранить каждую стоимость дважды (при условии, что она симметрична), но это верно во многих других подходах (включая матрицу).