掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.24650

迷路を解く方法
投稿者---くろ(2005/12/10 20:59:39)


プログラムで迷路を解く方法ってどんなのがありますか??
出来るだけ沢山の方法を知りたいんでお願いします!!!


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:迷路を解く方法 24654 かずま 2005/12/10 22:08:10
<子記事> Re:迷路を解く方法 24655 shu 2005/12/10 22:10:06
<子記事> Re:迷路を解く方法 24851 たいちう 2005/12/17 17:42:21


No.24654

Re:迷路を解く方法
投稿者---かずま(2005/12/10 22:08:10)


> プログラムで迷路を解く方法ってどんなのがありますか??

バックトラック。

具体的な迷路を与えてくれればプログラムを書いてさし上げますよ。


この投稿にコメントする

削除パスワード

No.24709

Re:迷路を解く方法
投稿者---かずま(2005/12/11 18:27:03)


/*
 * +---+---+---+---+---+
 * | 0   1   2 | 3   4 |
 * +   +   +---+---+   +
 * | 5 | 6   7   8 | 9 |
 * +   +   +---+   +   +
 * |10 |11  12 |13 |14 |
 * +---+---+   +   +   +
 * |15  16  17 |18  19 |
 * +---+---+---+---+---+
 */

#include <stdio.h>

enum { W = 5, START = 15, GOAL = 4 };
enum { U = 1, L = 2, R = 4, D = 8 };

char maze[20] = {
    R|D,   L|R|D, L,     R,     L|D,
    U|D,   U|R|D, L|R,   L|D,   U|D,
    U,     U|R,   L|D,   U|D,   U|D,
    R,     L|R,   U|L,   U|R,   U|L,
};

int route[20], check[20];

void step(int x, int n)
{
    if (check[x]) return;
    check[x] = 1;
    route[n++] = x;
    if (x == GOAL) {
        int i;
        for (i = 0; i < n; i++) printf(" %d", route[i]);
        printf("\n");
    } else {
        if (maze[x] & U) step(x - W, n);
        if (maze[x] & L) step(x - 1, n);
        if (maze[x] & R) step(x + 1, n);
        if (maze[x] & D) step(x + W, n);
    }
    check[x] = 0;
}

int main(void)
{
    step(START, 0);
    return 0;
}
説明が必要なら、どこが分からないのかを書いて質問してください。


この投稿にコメントする

削除パスワード

No.24849

Re:迷路を解く方法
投稿者---かずま(2005/12/17 15:00:38)


迷路をプログラムに組み込むと汎用性がないので、標準入力からファイルを
読むようにしました。ファイルのフォーマットは、

   マス目の総数  横の長さ  スタート  ゴール

   右に行けるマス R, 下に行けるマス D, 右にも下にも行けるマス B,
   それ以外 - (何でもよい)

---------------
20 5 15 4

BB-RD
DBRDD
-RDDD
RR-R-
---------------

例えば、上は次の迷路を表します。

+---+---+---+---+---+
| 0   1   2 | 3   4 |
+   +   +---+---+   +
| 5 | 6   7   8 | 9 |
+   +   +---+   +   +
|10 |11  12 |13 |14 |
+---+---+   +   +   +
|15  16  17 |18  19 |
+---+---+---+---+---+

----------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

enum { U = 1, L = 2, R = 4, D = 8, X = 0x10 };

unsigned int n, w, start, goal, *route;  char *maze;

int read_maze(void)
{
    unsigned int i;  char c;

    if (scanf("%u%u%u%u", &n, &w, &start, &goal) != 4) return 0;
    if (!n || !w || n % w != 0 || start >= n || goal >= n) return 0;
    maze = calloc(n, 1);
    route = malloc(n * sizeof(int));
    if (!maze || !route) return 0;
    for (i = 0; i < n; i++) {
        if (scanf(" %c", &c) != 1) return 0;
        switch (c) {
        case 'R': maze[i] |= R; maze[i+1] |= L; break;
        case 'B': maze[i] |= R; maze[i+1] |= L;
        case 'D': maze[i] |= D; maze[i+w] |= U; break;
        }
    }
    return 1;
}

void step(unsigned int x, int k)
{
    if (maze[x] & X) return;
    maze[x] |= X;
    route[k++] = x;
    if (x == goal) {
        int i;
        for (i = 0; i < k; i++) printf(" %u", route[i]);
        printf("\n");
    } else {
        if (maze[x] & U) step(x - w, k);
        if (maze[x] & L) step(x - 1, k);
        if (maze[x] & R) step(x + 1, k);
        if (maze[x] & D) step(x + w, k);
    }
    maze[x] &= ~X;
}

int main(void)
{
    if (read_maze()) step(start, 0);
    free(maze), free(route);
    return 0;
}



この投稿にコメントする

削除パスワード

No.24655

Re:迷路を解く方法
投稿者---shu(2005/12/10 22:10:06)


>プログラムで迷路を解く方法ってどんなのがありますか??

「迷路を解く方法」を考えて、それをプログラミングできれば、どんなのでもOK。


この投稿にコメントする

削除パスワード

No.24851

Re:迷路を解く方法
投稿者---たいちう(2005/12/17 17:42:21)


んじゃ、行き当たりばったり。

1)進む方法を乱数で選ぶ。
2)壁がなければ進む。
3)ゴールでなければ、1)に。


この投稿にコメントする

削除パスワード

No.24853

Re:迷路を解く方法
投稿者---塗り壁(2005/12/17 17:57:02)
http://www32.ocn.ne.jp/~graph_puzzle/index.html


>んじゃ、行き当たりばったり。
>
>1)進む方法を乱数で選ぶ。
>2)壁がなければ進む。
>3)ゴールでなければ、1)に。

それじゃ、アカデミックに。

1) 迷路グラフ(仮称)を作る。
2) 迷路グラフをスタートからゴールまで幅優先探索で辿る。

迷路グラフとは、各マスを頂点とし、二つのマスが隣接しているとき
辺で結んだもの。
ちなみに、グラフを使う利点は形を考慮する必要が無いこと。
正方形でも、円でも100角形でも同じ方式でできることですね。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧