プログラマ専用SNS ミクプラ

shims him さんが書きました: ↑

3年前

迷路の自動作成するプログラムを穴掘り法を用いて作成しようとしたのですが、スタートからゴールまでの道筋が複数本できてしまう場合があります。
どのように修正すれば良いのか、どなたかご教授願います。

コード:

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

#define N 21

#define ROAD 0
#define WALL 1
#define START 2
#define GOAL 3

int maze[N][N];

void set_maze();  //迷路初期化
void make_maze(); //迷路作成
void _maze(int x, int y); //ある位置から穴を掘る
void disp();              //迷路を画面に表示

int main()
{
    srand(time(NULL)); //乱数初期化

    set_maze();  //迷路初期化
    make_maze(); //迷路作成
    disp();      //迷路を表示
}

//迷路初期化
void set_maze()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            maze[i][j] = WALL;
        }
    }
    maze[1][0] = START;
    maze[N - 2][N - 1] = GOAL;
}

//迷路作成
void make_maze()
{ //穴掘り法
    int x, y;
    while (1)
    {
        x = 1 + rand() % (N - 2);
        if (x % 2 == 1)
            break;
    }
    while (1)
    {
        y = 1 + rand() % (N - 2);
        if (y % 2 == 1)
            break;
    }
    _maze(x, y);
}

//ある位置から穴を掘る
void _maze(int x, int y)
{
    int xp[4] = {0, 1, 0, -1};
    int yp[4] = {-1, 0, 1, 0};
    int d = rand() % 4;
    int temp = d;
    while (1)
    {
        int px = x + xp[d] * 2;
        int py = y + yp[d] * 2;
        if (px < 0 || px > N - 1 || py < 0 || py > N - 1 || maze[py][px] != WALL)
        {
            d = (d + 1) % 4;
            if (d == temp)
                return;
            continue;
        }
        maze[y + yp[d]][x + xp[d]] = ROAD;
        maze[py][px] = ROAD;
        _maze(px, py);
        d = rand() % 4;
        temp = d;
    }
}

//迷路を画面に表示
void disp()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (maze[i][j] == ROAD)
            {
                printf("  ");
            }
            else if (maze[i][j] == WALL)
            {
                printf("■ ");
            }
            else if (maze[i][j] == START)
            {
                printf("ス");
            }
            else if (maze[i][j] == GOAL)
            {
                printf("ゴ");
            }
        }
        printf("\n");
    }
}