3

筆記体のテキスト: 古いエントリ

通常のテキスト: 最新のエントリ

わかりましたので、int、より具体的には 0 と 1 の 2D 配列があります。もともとこれは BMP ファイル (白黒) でしたが、int の配列に変換しました。ここで、マトリックスは地図を表しており、0 は私が立つことができる場所 (床) であり、1 は深淵または壁 (1 では立つことはできません) です。したがって、この int のランダム配列を通過する必要がありますが、マップのすべての 0 を通過できる必要があります。「ピクセル」に複数回アクセスしても問題ありません。これのポイントは何ですか? マップ内の 4 つのキーを「隠す」メソッドがあり、キャラクターはマップ内でそれらを見つける必要があります。キャラクターが上下左右にしか動かない。斜め移動は許可されておらず、テレポートも許可されていません。これまでのところ、私はこのコードを持っています:

public void goThrough(int[,] map, int[] pos)
{
    int i = pos[0], j = pos[1]  ;
    while( i < map.GetLength(0) && j < map.GetLength(1) )
    {
        int cont = 0;
        if (map[i, j] == 0) 
        { 
            if (map[i, j + 1] == 0 && cont == 0 ) { j++; cont++; }
            if (map[i + 1, j] == 0 && cont == 0) { i++; cont++; }
            if (map[i, j - 1] == 0 && cont == 0 ) { j--; cont++; }
            if (map[i - 1, j] == 0 && cont == 0 ) { i--; cont++; }
        }
        if (map[i, j] == 1)
        {
        }
    }
}

public int[] Position(int[,] map)
{
    int[] pos = { 0, 0 };

    for (int i = 0; i < map.GetLength(0) && map[pos[0], pos[1]] == 1; i++)
    {
        for (int j = 0; j < map.GetLength(1) && map[pos[0], pos[1]] == 1; j++)
        {
            pos[0] = i;
            pos[1] = j;
        }
    }
    return pos;
}

明らかにいくつかの間違いがあります。フィードバックを送ってください。たぶん、この種のコードの経験がある人が私を少し助けることができます:D.

Edit1: 申し訳ありませんが、言語を指定しませんでした。これはC#です。簡単な更新も行います: 別の int[,] (最初のものとまったく同じ) を作成してみました。「エクスプローラー」が (x,y) を通過するたびに、この位置に one(1) を追加します（2番目、コピーされたもの）配列。このようにして、マップを完全に「探索」したことを認識するメソッドを作成できます。また、この「コピーされた」配列を使用すると、探索者が前にいた位置にいる場合、別の方向を選択できます (実際には、探索者がその地点を通過するたびに、そのスポットは 2 番目の配列で 0 にはなりません。配列内のその位置に 1 が追加されます)。アイデアは、探検家が同じ場所を 1 回、2 回、またはそれ以上通過したときに異なる動作をするようにすることですが、これはすべてまったく機能していません。私'

EDIT2：今、私はこのコードを持っています：

    public void goThrough(int[,] map, int[] pos, bool[,] visited)
    {
        int x = pos[0];
        int y = pos[1];
        visited[x, y] = true;
        Console.WriteLine("Position -> Column: {0} || Row: {1}", x, y);
        // ShowAtPosition(x, y)
        if (y > 0 && map[x, y - 1] == 0 && !visited[x, y - 1])
        {
            goThrough(map, new[] { x, y + 1 },visited); // north
            // ShowAtPosition(x, y)
        }
        if (x < map.GetLength(0) - 1 && map[x + 1, y] == 0 && !visited[x + 1, y])
        {
            goThrough(map, new[] { x + 1, y }, visited); // east
            // ShowAtPosition(x, y)
        }
        if (y < map.GetLength(1) - 1 && map[x, y + 1] == 0 && !visited[x, y + 1])
        {
            goThrough(map, new[] { x, y - 1 }, visited); // south
            // ShowAtPosition(x, y)
        }
        if (x > 0 && map[x - 1, y] == 0 && !visited[x - 1, y])
        {
            goThrough(map, new[] { x - 1, y }, visited); // west
            // ShowAtPosition(x, y)
        }
        if (NoZeros(visited)) { Console.WriteLine("I went through everything!"); Console.ReadLine(); }


    }

私が入れた WriteLine に注目してください。これにより、この再帰メソッドのすべての反復を追跡できます。これは出力です：

Position -> Column: 1 || Row: 31
Position -> Column: 2 || Row: 31
Position -> Column: 3 || Row: 31
Position -> Column: 4 || Row: 31
Position -> Column: 5 || Row: 31
Position -> Column: 6 || Row: 31
Position -> Column: 7 || Row: 31
Position -> Column: 8 || Row: 31
Position -> Column: 9 || Row: 31
Position -> Column: 10 || Row: 31
Position -> Column: 10 || Row: 32
Position -> Column: 11 || Row: 31
Position -> Column: 12 || Row: 31
Position -> Column: 13 || Row: 31
Position -> Column: 13 || Row: 32
Position -> Column: 14 || Row: 31
Position -> Column: 15 || Row: 31
Position -> Column: 16 || Row: 31
Position -> Column: 16 || Row: 32
Position -> Column: 17 || Row: 31
Position -> Column: 18 || Row: 31
Position -> Column: 19 || Row: 31
Position -> Column: 20 || Row: 31
Position -> Column: 21 || Row: 31
Position -> Column: 22 || Row: 31
Position -> Column: 23 || Row: 31
Position -> Column: 24 || Row: 31
Position -> Column: 25 || Row: 31
Position -> Column: 25 || Row: 30
Position -> Column: 1 || Row: 30

したがって、まず第一に、このメソッドはすべての迷路を通過せず、閉じることさえできませんでした (そして、0 はすべて接続されています)。

次に、最後の反復 (出力の最後の 2 行) で、エクスプローラーは (25,30) から (1,30) に「テレポート」しました。

ちなみに画像はこんな感じ。

白＝0、黒＝1

4

2 に答える 2

3

最初は、迷路を解くアルゴリズムを探しているだけのように思えます。左側のウォール フォロワーのようなものです。

ただし、迷路から抜け出す道を探しているのではなく、同じ値を持つすべての連続した場所を訪れようとしています。したがって、基本的にフラッド フィル アルゴリズムを使用できます。

唯一の落とし穴は、接続されていない の複数のプールがある可能性があることです0(すべての 0 が接続されるように元のビットマップが構築されていない限り、その場合、すべてのキーを配置するだけで到達可能であることを確認できます) 0 セル)。そのため、すべてがカバーされていることを確認するために、複数の開始点からフラッド フィルを実行する必要がある場合があります。

于 2013-04-21T22:51:12.597 に答える
1

遭遇する可能性のあるすべてのパスを含むツリーを作成できます。各ノードはマップ内の特定のポイントを表し、すべての子は移動できる有効なポイントを表します。訪問した各ポイントにはマークが付けられるため、再度訪問する必要はありません。次に、深さ優先のツリー検索を実行すると、可能なすべての場所を探索するまで歩き回ることができます。訪問したノードに遭遇するたびに、そこに再び行くことはありません。以下は、再帰的な深さ優先検索を実行します。大規模なマップの場合、非再帰的なソリューションが必要になるか、StackOverflowException が発生します。

private bool[,] visited; // needs to have same size as map
public void GoThrough(int[,] map, int[] pos) {
  int x = pos[0];
  int y = pos[1];
  visited[x, y] = true;
  // ShowAtPosition(x, y)
  if (y > 0 && map[x, y - 1] == 0 && !visited[x, y - 1]) {
    GoThrough(map, new [] {x, y - 1}); // north
    // ShowAtPosition(x, y)
  }
  if (x < map.GetLength(0) - 1 && map[x + 1, y] == 0 && !visited[x + 1, y]) {
    GoThrough(map, new [] {x + 1, y}); // east
    // ShowAtPosition(x, y)
  }
  if (y < map.GetLength(1) - 1 && map[x, y + 1] == 0 && !visited[x, y + 1]) {
    GoThrough(map, new [] {x, y + 1}); // south
    // ShowAtPosition(x, y)
  }
  if (x > 0 && map[x - 1, y] == 0 && !visited[x - 1, y]) {
    GoThrough(map, new [] {x - 1, y}); // west
    // ShowAtPosition(x, y)
  }
}

マップ全体と到達可能なすべてのタイルを通り抜けてから、開始点に戻ります。

基本的に、これは Matthew Strawbridge が (私が回答を入力しているときに) 言及したフラッド フィル アルゴリズムです。

于 2013-04-21T22:57:06.793 に答える