2

このリンクに示されているモバイル アプリケーション用のボード ゲームがあります: http://i45.tinypic.com/23u8u1h.png

開始点は任意のセルにすることができます。勝者は、自分の縦 (緑のプレーヤー) または横 (赤のプレーヤー) を接続した人です。

ノードは色付きのセルです。白血球は多分体重と見なすことができますか？実装方法はわかりませんが、ダイクストラ アルゴリズムを考えると、ボードがhttp://i50. tinypic.com/35ivofd.png (これらの 4 つの緑色のセルにアルゴリズムを適用する必要があります)

「 http://i48.tinypic.com/28c2ijl.png」の黒、茶、青、紫の経路が妥当な時間内で最短経路であることを教えてくれるアルゴリズムが必要です。

前もって感謝します。

4

1 に答える 1

0

Dijkstra はここで問題なく機能すると思います。特に、互いに隣接するフィールドを接続し、白以外の色で塗りつぶすために使用されるUnion Find アルゴリズムと組み合わせて使用​​すると効果的です。ホワイト フィールドにつながるエッジのコストは 1、自身のフィールドにつながるエッジのコストは 0、敵フィールドにつながるエッジのコストは無限 (例: mn ) です。次に、個々のフィールドを表すノードではなく、これらのフィールドの結合 (白以外のフィールドのクラスター) に対してDijkstraを実行します。

Dijkstra はここで約O(mn log^2(mn))で動作します。ここで、 nとmはボードの次元であり、Union Find はリンクの下部に記載されている単純な最適化でO(log mn)時間で動作します。論文。

于 2012-10-06T11:14:50.850 に答える