未初始化的变量 returns 分段错误

Question

说明：你的一个朋友正在研究旅行骑士问题 (TKP)，你要找到最短的封闭骑士移动之旅，它恰好访问棋盘上给定的 n 个方格集合中的每个方格一次。他认为问题中最困难的部分是确定两个给定方格之间的马移动的最小数量，一旦你完成了这个，找到环游就很容易了。你当然知道反之亦然。所以你让他写一个程序来解决 "difficult" 部分。你的工作是编写一个程序，将两个正方形 a 和 b 作为输入，然后确定马在从 a 到 b 的最短路径上移动的次数。

有多个测试用例。第一行包含一个整数T，表示测试用例的数量。每个测试用例由一行组成，其中包含由一个 space 分隔的两个方块。方块是一个字符串，由一个代表列的字母 (a-h) 和一个代表棋盘上的行的数字 (1-8) 组成。

对于每个测试用例，打印一行 "To get from xx to yy takes n knight moves."。 */

class Graph{
    int V;
    list<int> *adj;
public:
    //constructor, use adjacent list to represent the graph        
Graph(int V){
    V = V;
    adjacent = new list<int>[V];
}
void add(int i,int j){
    adjacent[i].push_back(j);
    adjacent[j].push_back(i);
}
// build the chess board
void add(int i){
    if(i + 1 >= 0 && i + 1 <= 63 && ((i + 1) / 8 == i / 8))                              
        add(i,i + 1);
    if(i + 7 >= 0 && i + 7 <= 63 && ((i + 7) / 8 == i / 8 + 1))
        add(i,i + 7);
    if(i + 8 >= 0 && i + 8 <= 63 && ((i + 8) / 8 == i / 8 + 1))
        add(i,i + 8);
    if(i + 9 >= 0 && i + 9 <= 63 && ((i + 9) / 8 == i / 8 + 1))
        add(i,i + 9);
}
//use BFS to find the shortest path from s to e
int BFS(int s ,int e){
    vector<bool> visited ;
    for(int i = 0; i < V; i++)
        visited.push_back(false);
    vector<int> distances;
    for(int i = 0; i < V; i++)
        distances.push_back(-1);
    distances[s] = 0;
    for(int current = 0; current < V; current++){
        for(int i = 0; i < V; i++){
            if( !visited[i] && distances[i] == current){
                visited[i] = true;
                if(i == e){
                    return distances[i];
                }
                for(list<int>::const_iterator k = adj[i].begin(); 
                    k != adj[i].end(); k++){
                    if(distances[*k] == -1){
                        distances[*k] = current + 1;
                    }
                }
            }
        }
   }
   return 0;
}
};
//test the BFS
int main(){
    Graph g(64);
    for(int i = 0; i < 64; i++){
        g.add(i);
    }
    cout << g.BFS(1,2);
    return 0;

}

Answer 1

以下代码使成员变量 V 处于未初始化状态，这可能是您出现问题的原因。

Graph(int V){
    V = V; // The LHS is the same as the RHS, the argument to the function
           // not the class member variable.
    adjacent = new list<int>[V];
}

使用：

Graph(int V) : V(V) {
    adjacent = new list<int>[V];
}

为了使代码更易于阅读，请为参数使用不同的名称。

Graph(int inV) : V(inV) {
    adjacent = new list<int>[V];
}

未初始化的变量 returns 分段错误

Variable without initialization returns segmentation fault

c++

graph

segmentation-fault

knights-tour