Невозможно ввести график

Question

Я решаю проблему http://www.spoj.com/problems/SHOP/ в C++, но я не могу понять, как вводить график для дальнейшего применения алгоритма Дейкстры в нем. Здесь граф Формат-
X 1 S 3
4 2 Х 4
Х 1 Д 2

Первая линия указаны столбцы & строки сетки,
"S" & «D» - указывает источник и назначение ресетически
Числа - указывает время, необходимое для прохождения этого блока, «X» - указывает зону входа без записи.
HOw для преобразования следующего графика в узлах и ребрах, как того требует алгоритм DIjkstra. Я не знаю, как преобразовать карту в граф.

Answer 1

Нет необходимости конвертировать. Представьте, что вы находитесь в какой-то точке (i, j). (Я предполагаю, что у вас есть четыре хода, разрешенных с каждого квадрата). Затем вы можете перейти к (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1), если:

1) Этот индекс находится внутри таблица 2) Этот индекс не обозначен X

Итак, вы указываете позицию квадрата S вашему алгоритму Дейкстры. И каждый раз, когда вы добавляете новый набор разрешенных квадратов в свою структуру данных. Как только вы достигнете положения D, вы распечатаете его.

Кроме того, эта проблема не выглядит взвешенной для меня, поэтому вы можете использовать простое BFS, а также использовать очередь. Но если вы хотите использовать Дийкстра и переходить в разные квадраты, то разные затраты. Вместо очереди вы используете очередь приоритетов. Например, вы можете использовать структуру набора данных, как это:

int dist[][]; // this contains the cost to get to some square 
//dist is initialized with a large number 

struct node{ 
    int i, j; //location 
    node(int ii, int jj){ 
     i = ii; 
     j = jj; 
    } 

    bool operator < (node &n)const{ //set in c++ will use this to sort 
     if(dist[i][j] == dist[n.i][n.j]) return i < n.i || j < n.j; //this is necessary 
     return dist[i][j] < dist[n.i][n.j]; 
    } 
}; 

set <node> q; 

int main(){ 
    //initialized dist with large number 
    dist[S.i][S.j] = 0; //we start from source 
    q.push(node(S.i, S.j)); 
    while(true){ 
     //pick the first element in set 
     //this element has the smallest cost 
     //update dist using this node if necessary 
     //for every node that you update remove from q and add it again 
     //this way the location of that node will be updated in q 
     //if you see square 'D' you are done and you can print dist[D.i][D.j] 
    } 

    return 0; 
} 

Answer 2

Нет необходимости преобразовывать матрицу в узлы и ребра. Вы можете создать структуру, которая содержит (номер строки, номер столбца, время), где время будет представлять, сколько времени требуется для достижения этой координаты из источника. теперь сделайте минимальную кучу этой структуры с ключом как время. теперь изначальный источник будет в мини-куче со временем как 0) из мини-кучи и нажимаем смежные элементы в кучу min (только те элементы, которые не посещаются и не содержат X), установленный посещенным извлеченным элементом true.Go например, до тех пор, пока выделенный элемент не будет назначен.