DouKaku? 5290 katsu: 速さには自信があります。(笑) >...(必ず解ける迷路)

Comment detail

This comment is reply for 5283 squld: 解いても楽しくない迷路になりそうですが、...(必ず解ける迷路). Go to thread root.

速さには自信があります。(笑)
>限られたメモリを使って縦方向に無限に広い迷路を
>どうやって作るのかを考えると答えが見えてくると思います。
をすっごくまじめに考えて、最小のメモリで無限の迷路を作り出すことばかり考えていたら、
こんなふざけたアイデアしか思いつかなかったので。
すみません。

メモリ使用量はO(1)なので確かに理想的ですね。速さも文句なしです。でも、さすがにそこまでのメモリ効率は想定していませんでした(笑)

他のコメントにも書きましたが、O(n)のアルゴリズムがあるんですよ。解いて楽しい迷路生成のメモリ効率としてはそれ以上のアルゴリズムは無いと踏んでます。時間のあるときにでも考えてみてください。

O(n)のアルゴリズムは、棒倒し法しか思いつかない。
穴掘り法はある程度、美しいんだけど、O(n^2)だし。

棒倒し法で棒を倒す方向を決定するのに、
周囲の環境を見て決めるように、パラメータチューニングするしかないのかなぁ。
と考え中。

↓は綺麗だけどお題を満たさない答え。　迷路(笑)

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

int main()
{
    int x,y,n,m;
    n = 10;
    m = 20;

    for (y = 0; y < m; y++){
        for (x = 0; x < n; x++){
            printf(rand() > RAND_MAX / 2 ? "／" : "＼");        
        }
        printf("\n");
    }
}

棒倒し法も空間計算量がO(n)なんですね。 O(nm)と勘違いしてました・・orz

ルールは満たしてませんが、見栄えのする迷路が出てきますね。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq