ラビリンスマトリクス

迷路を出るには再帰的またはスタック方式を用いることができ,ここではスタックの方法を採用し,迷路の行列は図のように,1は壁,0は道である

1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
0 0 0 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 1 1 1 
1 1 0 0 0 1 1 1 1 1 
1 0 0 1 0 1 1 1 1 1 
1 0 1 1 0 0 0 1 1 1 
1 0 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 1 1 1 1 

#include
#include

using namespace std;

const int n = 10;


int maze[n][n] = {0};
struct  Pos 
{
    int _row;
    int _col;
};
stack minStack;//      

void InitMaze(int maze[][n], int size)
{
    FILE* fOut = fopen("map.txt", "r");
    if(fOut == NULL)
    {
        cout<<"Open Maze.txt Fail"<exit(-1);
    }
    for (int i=0; ifor(int j=0; jchar ch = fgetc(fOut);
            if (ch == EOF)
            {
                cout<<"Maze Map Error!"<exit(-1);
            }
            if (ch == '1' || ch == '0')
            {
                maze[i][j] = ch - '0';
                ++j;
            }
        }
    }
    fclose(fOut);
}

int** f(int n)
{
    int** f = new int*[n];
    for (int i=0; inew int[n];
    }
    return f;
}

void PrintMaze(int maze[][n], int size)
{
    for(int i=0; ifor (int j=0; jcout<" ";
        }
        cout<cout<void PrintMinMaze(int maze[][n], int size, stack minStack)
{
    while (!minStack.empty())
    {
        Pos cur = minStack.top();
        maze[cur._row][cur._col] = 0;
        minStack.pop();
    }
    for(int i=0; ifor (int j=0; jcout<" ";
        }
        cout<cout<bool CheckIsAccess(int maze[][n], Pos cur)
{
    if (cur._row>=0 && cur._row =0 && cur._col0)
        return true;
    return false;
}

bool GetMazePath(int maze[][n], Pos entry, stack& paths)
{
    bool isMinPaths = false;
    paths.push(entry);
    maze[entry._row][entry._col] = 2;
    while (!paths.empty())
    {
        Pos cur = paths.top();
        Pos next = cur;
        if ((cur._row == n-1 || cur._col == n-1 
            || cur._col == 0 || cur._row == 0)
            &&(cur._col!=entry._col || cur._row!=entry._row))
        {
            isMinPaths = true;
            if(minStack.size()==0 || minStack.size()>paths.size())
                minStack = paths;
        }
        //  
        next._col -=1;
        if(CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row][next._col] = 2;
            continue;
        }
        //  
        next = cur;
        next._row -=1;
        if(CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row][next._col] = 2;
            continue;
        }
        //  
        next = cur;
        next._col +=1;
        if(CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row][next._col] = 2;
            continue;
        }
        //  
        next = cur;
        next._row +=1;
        if(CheckIsAccess(maze, next))
        {
            paths.push(next);
            maze[next._row][next._col] = 2;
            continue;
        }
        //  ，    
        Pos temp = paths.top();
        maze[temp._row][temp._col] = 3;//           3
        paths.pop();
    }
    return isMinPaths;
}

テストコード

#include "Maze.h"

int main()
{
    int mazeArray[n][n] = {0};
    InitMaze(mazeArray, n);
    PrintMaze(mazeArray, n);
    stack paths;
    Pos entry = {2,0};
    bool ret = GetMazePath(mazeArray, entry, paths);
    if (ret)
    {
        cout<<"      "<cout<<"    ："<