-1

だから私は入り口"2"から数字の1つへの最短の道を見つけるべきJavaプログラムを書いています"3"。位置のみを歩くことができ" "ます。"1"壁です。

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

私の最初のアイデアは、2次元配列の入り口を見つけることです。これは次のように実行できます。

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

2つを見つけて"3"ポイントに保存することもできました。しかし、ルートを最も近いものに戻す方法がわかりません"3"。私はジョイスティックのように考えていました。どこに行くかを保存します (UP、DOWN、LEFT、RIGHT)。次に、入り口から最も近い場所までの移動の完全なリストを返します 3. これを実装する方法について提案やアイデアはありますか?

4

3 に答える 3

2

ここにあるのは、グラフの非正規表現にすぎません。各セルがグラフの頂点であり、隣接する 2 つのセルが両方とも空いている場合に限り、それらの間にエッジがあります。

このように問題を調べたので、入口を見つけるのと同じように、幅優先探索を行って出口を見つけます。

于 2013-04-25T11:48:45.843 に答える
0

ノードとエッジを使用してグラフを作成しようとしました。ノードは迷路のジャンクションであり、エッジはジャンクションと入口または出口オブジェクト間のパスです。各エッジ オブジェクトには「重み」があります。二重配列からネットワークを計算したら、いくつかの簡単なアルゴリズムを使用して最短ルートを計算できます。

于 2013-04-25T11:49:58.550 に答える
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 に答える