突然兴起递归解决了走迷宫问题，对递归的本质加深了印象，一开始用到了STL的set容器，stl容器是排序容器，如果装载自定义对象的时候需要自定义排序函数，最后选择了用向量vector存储路径，vector有队列的性质。
解迷宫的递归流程是，检测四个方向是否可走，遇到死路则原路递归返回false,遇到出口则返回true，并将来的路线保存进队列。
#include#include #include #include int maze[10][15] = { {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,1,0,0,0,0,0,0,0,0,0,1}, {1,1,1,0,1,0,1,1,0,1,1,0,1,1,1}, {1,0,0,0,1,0,1,0,0,1,1,0,1,1,1}, {1,0,1,1,1,0,1,1,0,1,1,0,0,0,1}, {1,0,1,1,1,0,1,1,0,1,1,0,1,1,1}, {1,0,0,0,0,0,1,1,0,1,0,0,1,1,1}, {1,1,1,1,1,1,0,0,0,1,1,0,0,0,1}, {1,1,0,0,0,0,0,1,1,0,0,0,1,1,1}, {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1}};#define UP 1#define DOWN 2#define LEFT 3#define RIGHT 4struct SPoint{ int x; int y;};static int count = 0;//struct Compare{// bool operator() ( const SPoint& p1, const SPoint& p2) const// {// if (p1.x < p2.x)// {// return true;// }// else if (p1.x == p2.x)// {// if (p1.y < p2.y)// {// return true;// }// }// return false;// }//};bool walk(std::vector & routeVector, int srcDirect, SPoint nowPoint){ count++; // 已在路径中 /*for (std::vector ::iterator it = routeVector.begin(); it != routeVector.end(); ++it) { if ((*it).x == nowPoint.x && (*it).y == nowPoint.y) { return false; } }*/ // 已到达出口 if (1 == nowPoint.x && 0 == nowPoint.y ) { routeVector.push_back(nowPoint); return true; } int nowX = nowPoint.x; int nowY = nowPoint.y; SPoint nextPoint; bool passFlag = false; for(int direct = 1; direct <= 4; ++direct) { // 排除回头的方向 if (srcDirect == direct) { continue; } switch(direct) { case UP: { if (maze[nowY - 1][nowX] == 0) { nextPoint.x = nowX; nextPoint.y = nowY -1; if(walk(routeVector, DOWN, nextPoint)) { passFlag = true; } } break; } case DOWN: { if (maze[nowY + 1][nowX] == 0) { nextPoint.x = nowX; nextPoint.y = nowY +1; if(walk(routeVector, UP, nextPoint)) { passFlag = true; } } break; } case LEFT: { if (maze[nowY][nowX - 1] == 0) { nextPoint.x = nowX - 1; nextPoint.y = nowY; if(walk(routeVector, RIGHT, nextPoint)) { passFlag = true; } } break; } case RIGHT: { if (maze[nowY][nowX + 1] == 0) { nextPoint.x = nowX + 1; nextPoint.y = nowY; if(walk(routeVector, LEFT, nextPoint)) { passFlag = true; } } break; } default: break; } } if (passFlag) { routeVector.push_back(nowPoint); } return passFlag;}void print_maze(){ for (int raw = 0; raw < 10; ++raw) { for (int column = 0; column < 15; ++column) { if (maze[raw][column] == 1) { printf("■"); } else if(maze[raw][column] == 2) { printf("★"); } else { printf(" "); } if (column == 14) { printf("\n"); } } }}void paving(std::vector routeVec){ for (std::vector ::iterator it = routeVec.begin(); it != routeVec.end(); ++it) { int raw = (*it).y; int column = (*it).x; maze[raw][column] = 2; }}int main(int argc, char* argv[]){ for (int i = 0; i < argc; ++i) { printf("启动传入的参数: %s \n", argv[i]); } SPoint point; point.x = 9; point.y = 9; SPoint nextPoint; nextPoint.x = 9; nextPoint.y = 8; std::vector routeVec; walk(routeVec, DOWN, nextPoint); routeVec.push_back(point); paving(routeVec); print_maze(); printf("递归次数: %d", count); while(true);}