2

スライディングパズルを解く際に次の問題があります。パズルが解けるかどうか判断できる状態です。そして、空のタイトルを上下左右に移動する関数を既に作成しました。移動が可能な場合は 2D 配列を返し、そうでない場合は 0 を返します。初期構成を 2D 配列に格納します。

この問題を解決するために限定 DFS を選択しました。したがって、初期構成がルートになるツリー (またはリンクされたリスト) 構造体のようなものを作成する必要があります。次に、ゼロの位置に応じて (2,3 または 4) の子を持ちます。これらのノードには、次の構成で int **array (関数によって返される: toLeft、toRight、toUp、および toDown ) が含まれます。

したがって、再帰を使用して、目標の構成があるまで次のノードを作成できます。次に、ルートに「戻り」、手順を出力できます。例:
[5] LEFT
[7] UP
...
END

しかし、リンクされたリストの作成に問題があります。これまでのところ、私は次のものしか持っていません:

typedef struct Node{
int **array;
struct Node *left;
struct Node *right;
struct Node *up;
struct Node *down;
}Node;

ノードをリストに追加するにはどうすればよいですか?また、ノードが左、右、上、下のいずれであるかを判断するにはどうすればよいですか? ありがとうございました。

編集

アドバイス（削除された）で、コードを編集して新しい機能を追加しました...

   typedef struct Node{
    int **array;
    struct Node *left;
    struct Node *right;
    struct Node *up;
    struct Node *down;
    struct Node *parent;
    }Node;

Node* newNode(Node *parent, int **array){
    Node* u;
    u = malloc(sizeof(Node));
    if (u == NULL){
    printf("OUT OF MEMORY!");
    /* Free memory here.*/
    exit(1);
    }
    u->array = array;
    u->down = NULL;
    u->right = NULL;
    u->up = NULL;
    u->left = NULL;
    u->parent = parent;
    return u;
}

void setLeftNode(Uzel *parent, Uzel *child) {
  parent->left = child;
    }
/* setRightNode,Up,Down...*/


int isLeftChild (Node *node){
    if (node->parent == null) {return 0;}
    else{
        if (node->parent->left == node){return 1;}
        else{return 0;}
    }
}
/*is Right,Up,Down...*/

そして、ルートを追加しました: Node* root = newNode(NULL, array);

だから私の質問は次のとおり
です。
2. setLeftNode、setRightNode などを呼び出すにはどうすればよいですか?

お時間をいただきありがとうございます。:)

4

1 に答える 1

0

Spudd86に同意します。状態配列のツリーを明示的に構築する必要はありません。現在のパスにあるものだけで十分であり、それらはスタック上のポインターに保持できます。

おおよそ次のようなものが機能するはずです。

int dfs(int **state, int depthLimit, const char **steps) {
    if (isFinalState(state))
        return 1;

    if (depthLimit <= 0)
        return 0;

    int *newState;

    if (tryMoveLeft(state, &newState)) {
        if (dfs(newState, depthLimit, steps + 1)) {
            steps[0] = "left";
            freeState(newState);
            return 1;
        } else {
            freeState(newState);
        }
    }

    // The same for right, up, down ...

    // If no of the previous returns was taken, then this branch isn't the right one
    return 0;
}

isFinalState()状態が解かれたパズルに対応する場合はtryMoveLeft()戻り、左への移動が有効な場合は戻り、そうである場合は新しく割り当てられた状態を返しfreeState()、状態配列を解放する必要があります。出力は、検索を開始する前に十分なサイズに割り当てる必要がある配列 steps に格納されます。

これはあなたが尋ねたことに正確に答えるものではありませんが、とにかく役立つことを願っています:-D

于 2013-01-11T19:17:19.880 に答える