无法输入图形

Question

我正在用 C++ 解决问题 http://www.spoj.com/problems/SHOP/，但我无法弄清楚如何输入图形以进一步在其中应用 Dijkstra 算法。这是图形格式-
4 3
X 1 S 3
4 2 X 4
X 1 D 2

第一行表示网格的列和行，
"S" & "D" - 分别表示源和目标
数字 - 表示需要的时间通过该块，"X"-表示禁止进入区域。
如何按照 DIjkstra 的要求在节点和边中转换以下图形algorithm.I不知道如何将地图转换为图形。

Answer 1

不需要将矩阵转换为节点和边。您可以创建包含（行号、列号、时间）的结构，其中时间将表示从源到达该坐标所花费的时间。现在用键作为时间来制作这个结构的最小堆。现在从最小堆中提取元素（最初源将在最小堆中，时间为 0）并将相邻元素推入最小堆（仅那些未访问且不包含 X 的元素）设置已访问的提取元素 true.Go 像这样直到提取的元素不是目标。

Answer 2

不需要转换。想象一下你在某个点 (i,j)。（我假设您可以从每个方块进行四次移动）。然后，您可以转到 (i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1) 如果：

1) 该索引在 table 内 2) 该索引未标有 X

所以，你把方块S的位置给你的Dijkstra算法。每次您将一组新的允许方块添加到您的数据结构中时。一旦你到达 D 的位置，你就打印它。

此外，这个问题对我来说似乎并不重要，因此您也可以使用简单的 BFS 以及使用队列。但是如果你想使用 Dijkstra 并且去不同的广场有不同的成本。您使用优先级队列而不是队列。例如，您可以使用这样的集合数据结构：

 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;
}

无法输入图形

Unable to Input the graph

c++

algorithm

graph

dijkstra