-1

100 階建ての 10*10 の部屋を表現したいとします。どの階から始めても部屋の中を歩くことができますが、いくつかの階の間に壁があります.

CS について言えば、各正方形が床を表す 10*10 のグリッド (部屋) を作ろうとしています。各フロアには特定の特性があり、ノード、つまりグリッド全体として表すことができますが、これらのノードのリストが含まれています。

各正方形をそれに関連するものにリンクしようとしています。この関係は次のように記述できます。 -各正方形には、グリッドの端にあるものを除いて、上、右、上、下に別の正方形があります。

たとえば、グリッドの左上にある 1 階は、その右側の階とその下の階のみに関係があります。

・また、フロア間にブロックがある場合、フロア同士が連結できない場合があります。階数 前の例の 1 つとその下の 1 つをリンクすることはできません。それらの間には壁があるためです。

ポインターを使用して、各ノード (正方形または床) を関連するノードにリンクします。

public class Node{

private Node right;
private Node left;
private Node up;
private Node down;

//constructor other methods  
}

ただし、このソリューションは、100 個のノードがあり、各ノードに 4 つのポインターがあると仮定すると、メモリ内の多くの場所を取る可能性があります。

各ノードに ID を割り当てることでこのソリューションを変更しました。各ノードには、関連するノードの数を格納できる int[] 配列があります。

この解決策により、グリッド クラスに別の問題が発生しました。変更後、Node クラスの新しいメソッドは次のようになるとします。

public void setNeighbors(int[] neighbors ) { this.neighbors = neighbors; }

グリッド クラスで各ノードを作成してリストに追加する場合、各ノードに 1 行ずつ、100 行を記述する必要があります。

int [] n1 ={2}; grid.getEntry(1).setNeighbors(n1);
int [] n2 ={1,3}; grid.getEntry(2).setChars(n2 );
.
.
.
And so on..

私の質問は、できるだけ効率的でクリーンなコードを作成して問題を解決するにはどうすればよいかということです。

各ステップで配列を作成したり、100 行を記述したりせずに、正方形間の静的な関係をどのように表現できますか。

正方形間の数学的関係を見つけましたが、それらの間に壁があるためにいくつかの正方形が隣のオンセにリンクできないため、それを使用できませんでした..

4

2 に答える 2

1

微量のメモリを削減しようとする前に、動作するコードを取得することに集中する必要があると思います。これは時期尚早の最適化と呼ばれます。

「100 行の問題」を回避するには、次のようにしてフロアを初期化できます (未テスト)。

    Node[][] floor = new Node[10][10];
    for (int i=0;i<10;i++){
        for (int j=0;i<10;i++){
            floor[i][j] = new Node();
        }   
    }

    for (int i=0;i<10;i++){
        for (int j=0;j<10;j++){
            if (i<9)
                floor[i][j].down = floor[i+1][j];
            if (i>1)
                floor[i][j].up = floor[i-1][j];
            if (j<9)
                floor[i][j].right = floor[i][j+1];
            if (j>1)
                floor[i][j].up = floor[i][j-1];
        }   
    }
于 2013-11-04T19:24:01.507 に答える
0

ユークリッド距離の代わりにマンハッタン距離を計算できます。

于 2013-11-04T19:15:12.280 に答える