-3

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

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

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

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;

}

4

1 回答 1

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];
}
于 2015-06-12T01:07:22.327 回答