1 #include <iostream>  2 #include <queue>  3 #include <fstream>  4 #include <string>  5 #include <iomanip>  6   7 using std::cout;  8 using std::endl;  9 using std::cin; 10 using std::string; 11  12 class Maze 13 { 14 public: 15     Maze(string file); 16     ~Maze(); 17     void showMaze(void) const; 18     void getPath(void); 19     void calc(void); 20     void showPreNode(void) const; 21     void showPath(void) const; 22  23 private: 24     int m_rows; 25     int m_colomns; 26     bool** m_pData;        //用bool装迷宫数据 27  28     int** m_preNode;        //记录路径，也就是前一个节点 29     bool** m_flag;        //标志是否访问过 30     enum { INVALID = -1 }; 31      32     struct Coord        //定义一个坐标 33     { 34         int x; 35         int y; 36  37         bool operator ==(const Coord& rhs) 38         { 39             if (this->x == rhs.x && this->y == rhs.y) 40                 return true; 41             return false; 42         } 43     }; 44  45     void initeAboutCalc(void); 46     Coord getAssignCoord(const Coord& thisCoord, int num) const; 47     void showPathPre(int x, int y) const; 48 }; 49  50 Maze::Maze(string file) 51 { 52     std::ifstream fin(file); 53     fin >> m_rows >> m_colomns; 54  55     //分配数据区 56     m_pData = http://www.mamicode.com/new bool*[m_rows]; 57     for (int i = 0; i < m_rows; i++) 58         m_pData[i] = new bool[m_colomns]; 59  60     //读取数据 61     for (int i = 0; i < m_rows; i++) 62     { 63         for (int j = 0; j < m_colomns; j++) 64             fin >> m_pData[i][j]; 65     } 66  67     //初始化其他 68     initeAboutCalc(); 69 } 70  71 void Maze::initeAboutCalc(void) 72 { 73     m_preNode = new int*[m_rows]; 74     m_flag = new bool*[m_rows]; 75      76     for (int i = 0; i < m_rows; i++) 77     { 78         m_preNode[i] = new int[m_colomns]; 79         memset(m_preNode[i], INVALID, m_colomns * sizeof(int)); 80  81         m_flag[i] = new bool[m_colomns]; 82         memset(m_flag[i], false, m_colomns * sizeof(bool)); 83     } 84 } 85  86 Maze::~Maze() 87 { 88     for (int i = 0; i < m_rows; i++) 89         delete[] m_pData[i]; 90  91     delete[] m_pData; 92 } 93  94 void Maze::showMaze(void) const 95 { 96     for (int i = 0; i < m_rows; i++) 97     { 98         for (int j = 0; j < m_colomns; j++) 99             cout << m_pData[i][j] << " ";100 101         cout << endl;102     }103 }104 105 void Maze::calc(void)106 {107     const Coord START = { 0, 0 };108     const Coord END = { m_rows - 1, m_colomns - 1 };109     const Coord ERROR_COORD = { -1, -1 };110 111     std::queue<Coord> que;        //二维数组下标放到队列里面去112     m_flag[START.x][START.y] = true;113     que.push(START);        //起点114 115     while (true)116     {117         Coord thisNode = que.front();118         que.pop();119         if (thisNode == END)120             break;121 122         //对于这一点的上下左右个点123         for (int i = 0; i < 8; i++)124         {125             Coord coordTemp = getAssignCoord(thisNode, i);126             if (coordTemp == ERROR_COORD || 0 == m_pData[coordTemp.x][coordTemp.y])        //没有这点或者这点是墙127                 continue;128 129             if (!m_flag[coordTemp.x][coordTemp.y])        //没有访问过130             {131                 m_flag[coordTemp.x][coordTemp.y] = true;132                 m_preNode[coordTemp.x][coordTemp.y] = thisNode.x * m_colomns + thisNode.y;        //注意这里用的不是坐标了，但也可唯一确定一个点133                 que.push(coordTemp);134             }135         }136     }137 }138 139 Maze::Coord Maze::getAssignCoord(const Coord& thisCoord, int num) const140 {141     Coord res = { -1, -1 };        //不合法的142     if (num < 0 || num >= 4)143         return res;144 145     switch (num)146     {147     case 0:148         {149               if (!thisCoord.x)150                   return res;151               res.x = thisCoord.x - 1;152               res.y = thisCoord.y;153         }154     case 1:155         {156               if (thisCoord.y == m_colomns - 1)157                   return res;158               res.x = thisCoord.x;159               res.y = thisCoord.y +1;160         }161     case 2:162         {163               if (thisCoord.x == m_rows - 1)164                   return res;165               res.x = thisCoord.x + 1;166               res.y = thisCoord.y;167         }168     case 3:169         {170               if (!thisCoord.y)171                   return res;172               res.x = thisCoord.x;173               res.y = thisCoord.y - 1;174         }175     }176     return res;177 }178 179 void Maze::showPreNode(void) const180 {181     for (int i = 0; i < m_rows; i++)182     {183         for (int j = 0; j < m_colomns; j++)184             cout << std::setw(3) << std::left << m_preNode[i][j];185 186         cout << endl;187     }188 }189 190 void Maze::showPath(void) const191 {192     showPathPre(m_rows - 1, m_colomns - 1);193 }194 195 void Maze::showPathPre(int x, int y) const196 {197     if (0 == x && 0 == y)198     {199         cout << "(" << x << ", " << y << ")" << endl;200     }201     else202     {203         showPathPre(m_preNode[x][y] / m_colomns, m_preNode[x][y] % m_colomns);204         cout << " -> (" << x << ", " << y << ")" << endl;205     }206 }207 208 int main(void)209 {210     Maze maze("src.txt");211     maze.showMaze();212     cout << endl;213     maze.calc();214     maze.showPreNode();215     cout << endl;216     maze.showPath();217     cin.get();218 }