必ず解ける迷路 in C DouKaku?

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

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");
    }
}

反則だろうと思って投稿を思い止まっていたのにーｗ

棒を倒す方向を右か下に限定することによって
速度もコード量もそれなりではないかと思います☆

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define X 17
#define Y 15
int main(void){
  char maze[X - 1], *pattern[] = {"  ", "■"};
  int i, j;
  srand((unsigned)time(NULL));
  for(i = 0; i < X; i++)
    printf("■■");
  printf("■\n■%*s", X * 4 - 2, "");
  for(j = 0; j < Y - 1; j++){
    printf("■\n■  ");
    for(i = 0; i < X - 1; i++)
      printf("■%s", pattern[maze[i] = rand() / (RAND_MAX + 1.0) * 2]);
    printf("■\n■  ");
    for(i = 0; i < X - 1; i++)
      printf("%s  ", pattern[1 - maze[i]]);
  }
  printf("■\n■");
  for(i = 0; i < X; i++)
    printf("■■");
  printf("\n");
  return 0;
}

DouKaku?

必ず解ける迷路

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq