Ich kann das Diagramm nicht eingeben

Question

Ich löse das Problem http://www.spoj.com/problems/SHOP/ in C++, aber ich bin nicht in der Lage, herauszufinden, wie Sie das Diagramm eingeben, um den Dijkstra-Algorithmus anzuwenden. Hier ist der Graph Format-
X 1 S 3
4 2 X 4
X 1 D 2

Erste Zeile zeigte die Spalten & Zeilen des Rasters,
"S" & "D" - zeigt Quelle und Ziel an
Zahlen - zeigt die Zeit an, die benötigt wird, um diesen Block zu übergeben, "X" - zeigt die Zone ohne Eingabe an.
HOw zum Konvertieren der folgenden Grafik in Knoten und Kanten wie von DIjkstra-Algorithmus erforderlich.Ich weiß nicht, wie Sie die Karte in ein Diagramm konvertieren.

Answer 1

Es gibt keine Notwendigkeit zu konvertieren. Stellen Sie sich vor, dass Sie an einem Punkt sind (i, j). (Ich nehme an, dass Sie von jedem Feld aus vier Züge haben dürfen). Dann können Sie entweder (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1) wählen, wenn:

1) Dieser Index ist innen die Tabelle 2) Dieser Index ist nicht mit X markiert

So geben Sie die Position von Quadrat S zu Ihrem Dijkstra-Algorithmus. Und jedes Mal, wenn Sie die neue Menge erlaubter Quadrate zu Ihrer Datenstruktur hinzufügen. Sobald Sie die Position von D erreichen, drucken Sie es aus.

Außerdem scheint dieses Problem nicht zu mir gewichtet, so dass Sie eine einfache BFS sowie eine Warteschlange verwenden können. Aber wenn Sie Dijkstra benutzen und zu verschiedenen Plätzen gehen möchten, hat das unterschiedliche Kosten. Sie verwenden eine Prioritätswarteschlange statt einer Warteschlange. Zum Beispiel können Sie eine Reihe Datenstruktur wie folgt verwenden:

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

Es ist nicht notwendig, die Matrix in Knoten und Kanten zu konvertieren. Sie können eine Struktur erstellen, die (Zeilennummer, Spaltennummer, Zeit) enthält, wobei Uhrzeit angibt, wie viel Zeit benötigt wird, um diese Koordinate von der Quelle zu erreichen. Erstellen Sie nun einen Min-Heap dieser Struktur mit Schlüssel als Zeit. Jetzt extrahiere Element (anfänglich Quelle wird in Min-Heap mit Zeit als 0) von Min-Heap und schiebe die angrenzenden Elemente in Min-Heap (nur diejenigen Elemente, die nicht besucht werden und kein X enthalten) set visited des extrahierten Elements true.Go auf diese Weise, bis das extrahierte Element kein Ziel ist.