チェス盤外の隣接グラフの作成（ダイクストラ用）

Question

私は宿題に少し機能を追加したいという問題に遭遇しましたが、私にとって圧倒的なものでした（文脈のない質問のために大胆な文章を読んでください）。

私のプログラムには、約35項目のリストがあり、そこには私が扱うはずの地図に関する情報が入っています。 、ダイクストラでコード（X、Y）との重量100

「ツリー」を持つことになっている、その座標（X、Y）と

• 「ウォール」：これは、次の要素を持つことができます重量3

私は100枚のタイル、および35の項目を意味チェス盤、同じようにレイアウト10x10のマップを持っています。リスト内の「何もない」とは、ダイクストラのウェイト1を意味します（通常のルートを意味します）。

ダイクストラを機能させ、2つのタイル間の最短経路を見つけるには、隣接グラフを作成する必要があります。 ここに私の問題は、どのように私はすべてのリストがある場合、現在のタイルの "周り"タイルを定義する方法ですか？ 「+」の形をした

のみ隣接するタイルは、それら間のグラフのエッジを持っているが、それに何かがある場合、私はリストをチェックするたびに実行する必要がありますか？

コードサンプルでソースを指し示すことができれば、問題の鉛は大いにありがたく思います。私はそれを解決するために、多くの "if-elseif-elseif ..."で本当に面倒なコードしか見ません。

ありがとうございました！

編集：@kraskevichの提案方法を使用して終了しましたが、それは優れていますが、すべての回答と提案は本当に便利でした。皆さんありがとう！

Answer 1

グラフを作成する必要はありません。ただ、10x10テーブルを作成し、それに対応する項目の重みを置く：その後

board = 10x10 array filled with 1 
for item in list: 
    if item is a tree: 
     board[item.row][item.column] = 3 
    else if item is a wall: 
     board[item.row][item.column] = 100 

を、あなたは頂点としてペア座標の(row, col)を扱うことができますし、タイルを処理する際に4つの隣接するセルのための距離を更新します。それでおしまい。確かに、100個の頂点を持つグラフを作成し、タイルの明白なエッジを隣接する4つのセルすべてに追加することもできます（ウェイトはエッジタイルの終わりのウェイトです）。

次のように隣接するセルを反復処理するための最も便利な方法は次のとおりです。

delta_rows = [-1, 1, 0, 0] 
delta_cols = [0, 0, -1, 1] 
... 
for direction = 0 .. 3 
    new_row = row + delta_rows[direction] 
    new_col = col + delta_cols[direction] 
    if is_valid(new_row, new_col) 
      // do something 

Answer 2

この一般的なグラフインターフェイスに基づいてダイクストラを実装するのは簡単でなければなりません：

interface Graph<T> { 
    Iterable<T> adjacentNodes(T node); 
    double getDistance(T node, T adjacent); 
} 

だから今、私たちが必要とするすべてあなたのケースでそれを記入することです：

class Field { 
    final int x; 
    final int y; 
    int value = 1; 
    Field (int x, int y) { 
    this.x = x; 
    this.y = y; 
    } 
} 

class ChessboardGraph implements Graph<Field> { 
    Field[][] board = new Filed[10][10]; 

    ChessboardGraph(List<Entry> list) { 
    for (int x = 0; x < 10; x++) { 
     for (int y = 0; y < 10; y++) { 
     board[x][y] = new Field(x, y); 
     } 
    } 
    for (Entry e: list) { 
     board[e.x][e.y].value = e.value == TREE ? 3 : 100; 
    } 
    } 

    Iterable<Field> adjacentNodes(Field node) { 
    ArrayList result = new ArrayList<>(); 
    int x = node.x; 
    int y = node.y; 
    if (x > 0) { 
     if (y > 0) { 
     result.add(board[x - 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x - 1][y + 1]); 
     } 
    } 
    if (x < 9) { 
     if (y > 0) { 
     result.add(board[x + 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x + 1][y + 1]); 
     } 
    } 
    } 

    double getDistance(Field node, Field adjacent) { 
    assert Math.abs(node.x - adjacent.x) + Math.abs(node.y - adjacent.y) == 1; 
    return board[adjacent.x][adjacent.y]; 
    } 
}