-1

所以我正在编写一个 java 程序，它应该找到从入口"2"到其中一个数字的最短路径"3"。它只能在" "位置上行走。"1"是墙壁。

11111121 
131    1 
1 1 1111 
1 1 13 1     
1 1 11 1 
1 1    1
1      1  
11111111

我的开始想法是在二维数组中找到入口。这可以这样做：

Point entrance = new Point(0,0);
   for (int i = 0; i < N; i++) {
     for (int j = 0; j < N; j++){
        if(map[i][j] == 2){
           entrance.x =i;
           entrance.y =j;
        }
   }

我也可以找到这两个"3"并将它们保存在积分中。但我不确定如何将路线返回到最近的位置"3"。我正在考虑像一个操纵杆，我保存你去的方向，比如（上，下，左，右）。然后返回从入口到最近的移动的完整列表 3. 有什么建议或想法我可以如何实施？

4

3 回答 3

2

您在这里所拥有的只是图的非规范表示。您将每个单元格作为图中的一个顶点，并且当且仅当它们都是空闲的时，您在两个相邻单元格之间有一条边。

既然您以这种方式看待问题，请像您一样找到入口，而不是进行广度优先搜索以找到出口。

于 2013-04-25T11:48:45.843 回答
0

您需要创建一个计数器，每次当前位置为“”（可步行）时都会增加

符号" "=0在矩阵中：

Point entrance = new Point(0,0);
for (int i = 0; i < N; i++) {
 for (int j = 0; j < N; j++){
    if(map[i][j] == 2){
       entrance.x =i;
       entrance.y =j;
    }
}

Point firstexit = new Point(0,0);
int steps = 0;
int i = entrance.x;
int j = entrance.y;
int lasti = 0;
int lastj = 0;
while(true){

    if(map[i][j] == 3){
       firstexit.x =i;
       firstexit.y =j;
       break ;
    }
    if(map[i][j] == 0){
       steps++;
    }

    // TO-DO : check if position exists
    if(map[i][j+1] == 0 && (lasti != i && lastj != j)){
       lastj = j;
       j++;
    }else if(map[i][j-1] == 0 && (lasti != i && lastj != j)){
       lastj = j;
       j--;
    }else if(map[i+1][j] == 0 && (lasti != i && lastj != j)){
       lasti = i;
       i++;
    }else if(map[i-1][j] == 0 && (lasti != i && lastj != j)){
       lasti = i;
       i--;
    }

}
于 2013-04-25T11:48:23.480 回答
0

我会尝试创建一个带有节点和边的图。节点是迷宫中的连接点，边缘是连接点与入口或出口对象之间的路径。每个边缘对象都有一个“权重”。从双数组计算网络后，您可以使用一些简单的算法来计算出最短路径。

于 2013-04-25T11:49:58.550 回答