当前位置：首页 > news >正文

栈实现走出迷宫（C++）

news 来源：原创 2024/5/19 0:14:05

要求

将地图的数组保存在文件中，从文件中读取行列数
动态开辟空间保存地图
运行结束后再地图上标出具体的走法

说明

文件中第一行分别放置的是地图的行数和列数
其中1表示墙，即路不通，0表示路，即通路
程序运行结束后用2标记走过的路径
当走到“死胡同”时用3标记此路为死路
每到一个点，按照左上右下的顺序去试探
从入口直到找到出口为止，打印出走过的坐标
没有找到出口返回false

地图截图

图片描述

代码示例

maze.h

#ifndef MAZE_H_
#define MAZE_H_
#include <iostream>
#include <string>
#include <stack>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

#define WALL 1
#define ROAD 0
#define SUCCESS 1;
#define ERROR 0;

class Seat{
public:
    Seat() // 无参构造函数 坐标默认 （0,0）
        :m_iX(0)
        ,m_iY(0)
    {}

    Seat(int x, int y) // 有参构造函数
        :m_iX(x)
        ,m_iY(y)
    {}

    bool operator==(const Seat &other){ // 重载坐标相等
        if(m_iX == other.m_iX && m_iY == other.m_iY)
            return true;
        return false;
    }

    int m_iX;
    int m_iY;
};


class Maze {
private:
    int** m_ppMap; // 指向地图的指针
    int m_iRow; // 存放地图的行数
    int m_iCol; // 存放地图的列数
public:
    Maze(const string& filePath); // 构造函数 初始化迷宫
    bool PassMaze(stack<Seat>& s, Seat& start, Seat& end); // 走出迷宫
    void PrintMap(); // 打印迷宫
    virtual ~Maze(); // 析构函数 释放内存
private:
    bool isPass(Seat& entry); // 判断是否为通路
};

#endif /* MAZE_H_ */

maze.cpp

#include "Maze.h"
#include <typeinfo>

Maze::Maze(const string& filePath) {
    fstream mapFile(filePath, ios::in);

    if(!mapFile.is_open()){
        cout << "读取文件失败" << endl;
    }

    string str_row_col; //第一行  获取行和列
    string str_temp;  // 临时字符串
    getline(mapFile, str_row_col);

    // 获取行列的个数
    str_temp = str_row_col.substr(0, str_row_col.find_first_of(','));
    m_iRow = atoi(str_temp.c_str());
    str_temp = str_row_col.substr(str_row_col.find_first_of(',')+1); // 取得字符串中的列数
    m_iCol = atoi(str_temp.c_str());

    // 分配空间
    m_ppMap = new int*[m_iRow];
    for(int i = 0; i < m_iRow; ++i){
        m_ppMap[i] = new int[m_iCol];
    }

    // 填充地图
    int index_row = 0; // 放置地图 二维数组的行索引
    int index_col = 0; // 放置地图 二维数组的列索引
    while(! mapFile.eof()){
        getline(mapFile, str_temp);
        char* a_line = (char*)str_temp.c_str();

        while(*a_line != '\0'){
            if(*a_line == '0' || *a_line == '1'){
                m_ppMap[index_row][index_col++] = *a_line - '0';
            }
            a_line++;
        }
        ++index_row;
        index_col = 0;
    }

    mapFile.close();


}

bool Maze::PassMaze(stack<Seat>& s, Seat& start, Seat& end) {

    if( !isPass(start) ){
        return false;
    }

    s.push(start);//压栈当前位置

    while(!s.empty()){// 栈不为空继续

        // 取得栈顶存储的位置
        Seat curSeat = s.top();

        // 走到边界
        if(curSeat.m_iX < 0 || curSeat.m_iY < 0
                || curSeat.m_iX > m_iRow || curSeat.m_iY > m_iCol){
            return false;
        }

        // 将走过的路标记为2
        m_ppMap[curSeat.m_iX][curSeat.m_iY] = 2;

        //找到出口
        if(curSeat == end){
            return true;
        }
        // 往左走
        Seat left(curSeat.m_iX, curSeat.m_iY - 1);
        if(isPass(left)){
            s.push(left);
            continue;
        }
        // 往上走
        Seat top(curSeat.m_iX - 1, curSeat.m_iY);
        if(isPass(top)){
            s.push(top);
            continue;
        }
        // 往右走
        Seat right(curSeat.m_iX, curSeat.m_iY + 1);
        if(isPass(right)){
            s.push(right);
            continue;
        }
        // 往下走
        Seat down(curSeat.m_iX + 1, curSeat.m_iY);
        if(isPass(down)){
            s.push(down);
            continue;
        }

        // 运行到此处说明 每个方向都没有路可走 是死路标记为3
        m_ppMap[curSeat.m_iX][curSeat.m_iY] = 3;
        s.pop();
    }

    return true;
}

void Maze::PrintMap() {
    for(int index_row = 0; index_row < m_iRow; index_row++){
        for(int index_col = 0; index_col < m_iCol; index_col++){
            cout << m_ppMap[index_row][index_col] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

Maze::~Maze() {
   for (int i = 0; i < m_iRow; ++i  )
    {
        delete[] m_ppMap[i];
    }
    delete[] m_ppMap;
    m_ppMap = NULL;
}

bool Maze::isPass(Seat& entry) {

    // 边界
    if(entry.m_iX < 0 || entry.m_iY < 0
            || entry.m_iX >= m_iRow || entry.m_iY >= m_iCol){
        return false;
    }

    if(m_ppMap[entry.m_iX][entry.m_iY] == 0){
        return true;
    }

    return false;
}

main.cpp

#include <iostream>
#include <string>
#include "Maze.h"

using namespace std;

int main() {

    Maze m1("src/map.txt");
    Seat start(0,8); // 开始坐标
    Seat end(9,2); // 结束坐标
    stack<Seat> s;
    m1.PassMaze(s, start, end);
    m1.PrintMap();

    cout << "走过的坐标：" << endl;
    while(!s.empty()){
        Seat temp = s.top();
        cout << "(" << temp.m_iX <<","<< temp.m_iY << ")"<< ",";
        s.pop();
    }

    return 0;
}