迷路

Posted at 2026-08-27

課題

　迷路(7×7=49マス)のスタート(S=0)からゴール(G=48)までの道順を解くプログラムを作成せよ.

迷路データ

Problem.txt

　上記の迷路データは以下の迷路イメージに対応する．例えば, 迷路データ1行目の「0 1 1 0 0」は，左から「ブロック番号」，「上」，「右」，「下」，「左」を表しており，「上」，「右」，「下」，「左」は，1の場合は線有り，0の場合は線無しを表す．この場合，ブロック番号0(スタート地点)は└となる．

記号	上	右	下	左
│	1	0	1	0
┼	1	1	1	1
┘	1	0	0	1
└	1	1	0	0
┐	0	0	1	1
┌	0	1	1	0
┤	1	0	1	1
├	1	1	1	0
┴	1	1	0	1
┬	0	1	1	1

あらかじめ与えられた解答

13ブロック経由
0(S) → 1 → 8 → 15 → 16 → 23 → 30 → 31 → 32 → 39 → 40 → 41 → 48(G)

プログラム

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

#define SIZE 49 // 迷路サイズ

// 迷路ブロックを表す構造体
// 今更だがpeaceよりblockの方がいいかもしれない・・・
typedef struct peace{
   int num;   // 何番目のブロックか
   int up;
   int right;
   int down;
   int left;
}Peace;

// ファイルからデータを読み込む関数
void readData(Peace[], int);

// ゴールまでの道のりを探索する関数
void solution(Peace [], int, int);

// 探索データをファイルに出力する関数
void writeData(int);

int buf[13]; // ゴールまで通った道筋を格納する
int next;    // 次の格納位置

int main()
{
    Peace data[SIZE];

    // ファイルからデータを読み込む
    readData(data, SIZE);

    // ゴールまでの道のりを探索する
    solution(data, 0, 0);
 
    return 0;
}

// ファイルからデータを読み込む関数
void readData(Peace data[], int size)
{
    FILE *readPtr;
    int i;

    if ((readPtr = fopen("Problem.txt", "r")) == NULL)
    {
        //fprintf(stderr, "readData Error\n");
        exit(-1);
    }

    for (i = 0; i < size; i++)
    {  
        fscanf(readPtr, "%d %d %d %d %d\n", &data[i].num, &data[i].up, 
                         &data[i].right,&data[i].down, &data[i].left);
    }
    fclose(readPtr);
}

// ゴールまでの道のりを探索する関数
void solution(Peace d[], int nowP, int preP)
{
    int i;

    // ゴールに到達したら
    if (nowP == 48)
    {
        //printf("48 goal\n");
        buf[next] = 48;
        next++;

        // ファイルに通った経路を書き出す
        writeData(next);    
        // ゴールに到達した後, returnで1段戻っても, 
        // その上の再帰呼び出しは引き続き他の分岐を探索することに注意
        return;
     }

    //printf("%d ", nowP);

    if (d[nowP].up == 1 && (nowP - 7) != preP)
    { 
        if (d[nowP - 7].down == 1 && nowP - 7 >= 0)
        {
           buf[next] = nowP;
           next++;
           solution(d, nowP - 7, nowP);
        }
        else
        {
           //printf("stop\n");
        }
    }

    if (d[nowP].right == 1 && (nowP + 1) != preP)
    {
       if (d[nowP + 1].left == 1 && (nowP + 1) % 7 != 0)
       { 
           buf[next] = nowP;
           next++;
           solution(d, nowP + 1, nowP);
       }
       else
       {
           //printf("stop\n");
       }
    }

    if (d[nowP].down == 1 && (nowP + 7) != preP)
    {
       if (d[nowP + 7].up == 1 && nowP + 7 < 49)
       {   
           buf[next] = nowP;
           next++;
           solution(d, nowP + 7, nowP);
       }
       else
       {
          //printf("stop\n");
       }
    }

    if (d[nowP].left == 1 && (nowP - 1) != preP)
    {
       if (d[nowP - 1].right == 1 && nowP % 7 != 0)
       { 
           buf[next] = nowP;
           next++;
           solution(d, nowP - 1, nowP);
       }
       else
       {
           //printf("stop\n");
       }
    }
    
    // どの方向にも進めなかったので戻る
    next--;
    return;
}

// 探索データをファイルに出力する関数
void writeData(int size)
{
   int i;
   FILE *writePtr;

   if ((writePtr = fopen("Answer.txt", "w")) == NULL)
   {
        //fprintf(stderr, "Answer.txt error\n");
        exit(-1);
   }

   for (i = 0; i < size; i++)
   { 
      fprintf(writePtr, "%d\n", buf[i]);
   }
   fclose(writePtr);
}

実行結果

Answer.txt

解説

　まず, 迷路ブロックを格納する構造体を定義した.

// 迷路ブロックを表す構造体
typedef struct peace{
   int num;   // 何番目のブロックか
   int up;
   int right;
   int down;
   int left;
}Peace;

迷路を構成する49ブロックの上, 右, 下, 左, 4方向の道の情報を格納する. 1: 道あり, 0: 道なしである. numはブロック番号格納用である.

　次に、迷路データが格納されたファイルから構造体配列に迷路データを読み込むreadData関数を以下のように定義した.

// ファイルからデータを読み込む関数
void readData(Peace data[], int size)
{
    FILE *readPtr;
    int i;

    if ((readPtr = fopen("Problem.txt", "r")) == NULL)
    {
        //fprintf(stderr, "readData Error\n");
        exit(-1);
    }

    for (i = 0; i < size; i++)
    {  
        fscanf(readPtr, "%d %d %d %d %d\n", &data[i].num, &data[i].up, 
                         &data[i].right,&data[i].down, &data[i].left);
    }
    fclose(readPtr);
}

この関数ではfopen関数を使ってProblem.txtを読み込みモードで開き,fscanf関数を使ってファイルの迷路データを構造体配列dataに読み込む. 呼び出し元で引数をSIZE(=49)と与えているため, 49個の迷路ブロックを順に取り込む. データを読み込んだ後は, fclose関数でファイルを閉じる.

　データを読み込んだら, 次はゴールまでの道のりを探索してファイルに出力しなければならない. ゴールまでの道のりを探索する関数solutionを定義し, 迷路を解いた結果を外部配列bufに記録する.

// 迷路を探索する関数
void solution(Peace d[], int nowP, int preP)
{
    int i;

    // ゴールに到達したら
    if (nowP == 48)
    {
        //printf("48 goal\n");
        buf[next] = 48;
        next++;

        // ファイルに通った経路を書き出す
        writeData(next);    
        return;
     }

    //printf("%d ", nowP);

    if (d[nowP].up == 1 && (nowP - 7) != preP)
    { 
        if (d[nowP - 7].down == 1 && nowP - 7 >= 0)
        {
           buf[next] = nowP;
           next++;
           solution(d, nowP - 7, nowP);
        }
        else
        {
           //printf("stop\n");
        }
    }

    if (d[nowP].right == 1 && (nowP + 1) != preP)
    {
       if (d[nowP + 1].left == 1 && (nowP + 1) % 7 != 0)
       { 
           buf[next] = nowP;
           next++;
           solution(d, nowP + 1, nowP);
       }
       else
       {
           //printf("stop\n");
       }
    }

    if (d[nowP].down == 1 && (nowP + 7) != preP)
    {
       if (d[nowP + 7].up == 1 && nowP + 7 < 49)
       {   
           buf[next] = nowP;
           next++;
           solution(d, nowP + 7, nowP);
       }
       else
       {
          //printf("stop\n");
       }
    }

    if (d[nowP].left == 1 && (nowP - 1) != preP)
    {
       if (d[nowP - 1].right == 1 && nowP % 7 != 0)
       { 
           buf[next] = nowP;
           next++;
           solution(d, nowP - 1, nowP);
       }
       else
       {
           //printf("stop\n");
       }
    }
    
    // どの方向にも進めなかったので戻る
    next--;
    return;
}

この関数では再帰処理を利用して迷路を探索する. まず, 現在迷路のどの位置にいるかを表す変数nowPが48, すなわち, ゴールの場合にはその値を外部配列bufに格納する.

格納前までの段階でbufにはゴール一歩手前までの道筋が格納されているため, 後で説明するwriteData関数を使って全経路をファイルに出力する.

一方, 現在の位置がゴール以外ならば迷路の探索を続ける. 移動先は4方向移動先が存在し, 例えば, 以下は現在の位置から上方向に迷路を探索する.

if (d[nowP].up == 1 && (nowP - 7) != preP)
{ 
    if (d[nowP - 7].down == 1 && nowP - 7 >= 0)
    {
        buf[next] = nowP;
        next++;
        solution(d, nowP - 7, nowP);
    }
    else
    {
        //printf("stop\n");
    }
}

最初の条件文では, 現在の位置のブロックが上方向への道を持っているか, さらに、(nowP - 7) != prePにより, 上方向に進んだ先が1つ前にいた位置と一致しないことを確認している. 来た道をそのまま戻ることはあってはならない.

次の条件文では, 1つ上の迷路データが下方向への道を持っていること, nowP - 7 >= 0によって迷路の外へ出ないことを確認している.

これらの条件を満たした場合, 外部配列bufに現在のブロック番号を格納し, 次にブロックを格納する位置を表す配列インデックス変数nextを1つ増やす. その後,

solution(d, nowP - 7, nowP);

によりsolution関数を再び呼び出す.

void solution(Peace d[], int nowP, int preP)

引数としてnowPには次に移動する位置をprePには現在の位置を渡す. これにより, 移動先でも同じ処理を繰り返し, ゴールまで探索を続ける. 右, 下, 左方向の場合も基本的にはこれと同様である.

再掲となるが, 道筋が配列bufに格納される条件は以下の3つである.

現在の位置から探索する方向に道が存在する
その方向に進んでも迷路の外へ出ない
その方向へ進むことが直前の位置へ戻ることにならない

これら条件を満たした場合, そのブロック番号をbufに記録して次の位置へ移動する. どの方向にも進めない場合には, 再帰呼び出し元に処理が戻る. 戻る前にnext--とすることにより, 戻った先から新しい道筋の書き込みが可能となる.

// どの方向にも進めなかったので戻る
next--;
return;

以上が迷路を探索する関数solutionである.

　最後にゴールまでの道筋をファイルへ出力する関数writeDataを説明する. まず, fopen関数を使ってAnswer.txtを書き込みモードで開く. その後, for文によって外部配列bufに格納された道筋を順番に取り出し, fprintf関数で1行ずつファイルへ出力する. ループ処理の後はfclose関数によりファイルを閉じる.

// 探索データをファイルに出力する関数
void writeData(int size)
{
   int i;
   FILE *writePtr;

   if ((writePtr = fopen("Answer.txt", "w")) == NULL)
   {
        //fprintf(stderr, "Answer.txt error\n");
        exit(-1);
   }

   for (i = 0; i < size; i++)
   { 
      fprintf(writePtr, "%d\n", buf[i]);
   }
   fclose(writePtr);
}

以上が迷路を解くプログラムである.

ポータルサイト

https://qiita.com/Yuta_Nakamura_/items/4facb3521054dcb2e288

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

記号	上	右	下	左
│	1	0	1	0
┼	1	1	1	1
┘	1	0	0	1
└	1	1	0	0
┐	0	0	1	1
┌	0	1	1	0
┤	1	0	1	1
├	1	1	1	0
┴	1	1	0	1
┬	0	1	1	1

記号	上	右	下	左
│	1	0	1	0
┼	1	1	1	1
┘	1	0	0	1
└	1	1	0	0
┐	0	0	1	1
┌	0	1	1	0
┤	1	0	1	1
├	1	1	1	0
┴	1	1	0	1
┬	0	1	1	1

記号	上	右	下	左
│	1	0	1	0
┼	1	1	1	1
┘	1	0	0	1
└	1	1	0	0
┐	0	0	1	1
┌	0	1	1	0
┤	1	0	1	1
├	1	1	1	0
┴	1	1	0	1
┬	0	1	1	1