거 슬러 올 라 가 미궁 을 구하 다.

우선 Mazemap. txt 파일 에 미 로 를 만 듭 니 다.0 은 갈 수 있 는 길 을 의미 하고, 1 은 통 하지 않 는 길 을 의미한다.
먼저 구조 체 를 정의 하여 좌 표를 저장 합 니 다.

template
class Maze
{
public:
    Maze(int maze[M][N])
    {
        for (size_t i = 0; i < M; ++i)
        {
            for (size_t j = 0; j < N; ++j)
            {
                _maze[i][j] = maze[i][j];
            }
        }
    }

    struct Pos
    {
        int _row; //  
        int _col; //  
    };

함 수 를 만들어 서 내 려 갈 수 있 는 지 없 는 지 를 판단 하고 그 위치 가 0 인지 아 닌 지 를 판단 합 니 다.

bool CheckAccess(Pos next)
    {
        if ((next._row >= 0 && next._row < M)
            &&(next._col >= 0 && next._col <= N)
            && _maze[next._row][next._col] == 0)
        {
            return true;
        }

        return false;
    }

이어서 해답 을 구하 다

bool GetMazePath(Pos entry)
    {
        stack paths;
        paths.push(entry);

        while (!paths.empty())
        {
            //            
            Pos cur = paths.top();
            _maze[cur._row][cur._col] = 2;

            //      
            if (cur._row == M-1)
            {
                return true;
            }

            //       
            //  
            Pos next = cur;
            next._row -= 1;
            if(CheckAccess(next))
            {
                paths.push(next);
                continue;
            }


            //  
            next = cur;
            next._col += 1;
            if(CheckAccess(next))
            {
                paths.push(next);
                continue;
            }


            //  
            next = cur;
            next._row += 1;
            if(CheckAccess(next))
            {
                paths.push(next);
                continue;
            }

            //  
            next = cur;
            next._col -= 1;
            if(CheckAccess(next))
            {
                paths.push(next);
                continue;
            }

            Pos back = paths.top();
            _maze[back._row][back._col] = 3;
            paths.pop();
        }

        return false;
    }

bool GetMazePathR(Pos entry)
    {
        Pos cur = entry;
        _maze[cur._row][cur._col] = 2;
        //       
        if (entry._row == N-1)
        {
            return true;
        }

        Pos next = cur;

        //  
        next._row -= 1;
        if (CheckAccess(next))
        {
            //    
            if (GetMazePathR(next))
                return true;            
        }

        //  
        next = cur;
        next._col += 1;
        if (CheckAccess(next))
        {
            if (GetMazePathR(next))
                return true;
        }

        //  
        next = cur;
        next._row += 1;
        if (CheckAccess(next))
        {
            if (GetMazePathR(next))
                return true;
        }

        //  
        next = cur;
        next._col -= 1;
        if (CheckAccess(next))
        {
            if (GetMazePathR(next))
                return true;
        }

        // 
        _maze[cur._row][cur._col] = 3;
        return false;
    }

검 측 을 위해 함 수 를 계속 구축 합 니 다.

bool CheckAccess(Pos next, Pos cur)
    {
        if ((next._row >= 0 && next._row < M)
            &&(next._col >= 0 && next._col <= N))
        {
            if (_maze[next._row][next._col] == 0)
            {
                return true;
            }
            else if (_maze[next._row][next._col] == 1)
            {
                return false;
            }
            else
            {
                return _maze[next._row][next._col] > _maze[cur._row][cur._col]+1;
            }
        }
        else
        {
            return false;
        }
    }

다음 최 단 경로 구하 기

void GetShortPath(Pos entry,
        stack& path, stack& shortPath)
    {
        Pos cur = entry;
        path.push(cur);

        //       
        if (entry._row == N-1)
        {
            Print();
            if (shortPath.empty() || path.size() < shortPath.size())
            {
                shortPath = path;
            }
        }

        Pos next = cur;

        //  
        next._row -= 1;
        if (CheckAccess(next, cur))
        {
            //    
            _maze[next._row][next._col] = _maze[cur._row][cur._col] + 1;
            GetShortPath(next, path, shortPath);            
        }

        //  
        next = cur;
        next._col += 1;
        if (CheckAccess(next, cur))
        {
            _maze[next._row][next._col] = _maze[cur._row][cur._col] + 1;
            GetShortPath(next, path, shortPath);            
        }

        //  
        next = cur;
        next._row += 1;
        if (CheckAccess(next, cur))
        {
            _maze[next._row][next._col] = _maze[cur._row][cur._col] + 1;
            GetShortPath(next, path, shortPath);            
        }

        //  
        next = cur;
        next._col -= 1;
        if (CheckAccess(next, cur))
        {
            _maze[next._row][next._col] = _maze[cur._row][cur._col] + 1;
            GetShortPath(next, path, shortPath);            
        }

        path.pop();
    }

나머지 코드 는 다음 과 같다.

protected:
    int _maze[M][N];
};

void ReadMaze(int maze[10][10])
{
    FILE* fout = fopen("MazeMap.txt", "r");
    assert(fout);

    for (size_t i = 0; i < 10; ++i)
    {
        for (size_t j = 0; j < 10;)
        {
            char ch = fgetc(fout);
            if (ch == '0' || ch == '1' || ch == '2')
            {
                maze[i][j] = ch - '0';
                ++j;
            }
        }
    }
}

void TestMaze()
{
    //             ？
    //               ？
    //       --          ？
    int maze[10][10];
    ReadMaze(maze);

    Maze<10, 10> m(maze);
    Maze<10, 10>::Pos entry;
    entry._row = 2;
    entry._col = 0;
    //m.GetMazePath(entry);
    //cout<

    stack::Pos> path, shortPath;
    m.GetShortPath(entry, path, shortPath);
    //m.Print();
}

미궁 구 해 는 데이터 구조의 학습 에 큰 도움 이 되 었 습 니 다. 이 코드 는 저 는 일주일 여 동안 작성 하고 이 해 했 습 니 다. 처음에 약간 은 완전히 이해 하지 못 했 습 니 다. 매일 여러 번 생각 하고 테스트 를 한 후에 마지막 으로 썼 습 니 다.나 처럼 이 부분 을 공부 하고 있 는 학우 들 이 많이 생각 하고 온고지신 하 기 를 바란다.