#include堆栈实现#include #define CRT_SECURE_NO_WARINGS #pragma warning(disable:6011) #pragma warning(disable:6386) struct position { int x; int y; }; struct position pathstack[100]; int stackTop = -1; int size = 0; int** maze = NULL; int** makearray(int row,int cols) { int** array = (int**)malloc(sizeof(int*) * row); for (int i = 0; i < row; i++) { array[i] = (int*)malloc(sizeof(int) * cols); } return array; } void creatmap() { printf("请输入迷宫的大小:n"); scanf_s("%d", &size); maze = makearray(size+2,size+2); printf("请输入迷宫:n"); for (int i = 1; i <= size; i++) { for (int j = 1; j <= size; j++) { scanf_s("%d", &maze[i][j]); } } //加边框; for (int i = 0; i <= size + 1; i++) { maze[0][i] = maze[size + 1][i] = 1; maze[i][0] = maze[i][size + 1] = 1; } } //findroad找路径; int findpath() { struct position offset[4];// = { {0,1},{1,0},{0,-1},{-1,0} }; offset[0].x = 0; offset[0].y = 1; offset[1].x = 1; offset[1].y = 0; offset[2].x = 0; offset[2].y = -1; offset[3].x = -1; offset[3].y = 0; struct position here = { 1,1 }; pathstack[++stackTop] = here; maze[1][1] = 1; int option = 0; int endoption = 3; while (here.x != size || here.y != size) { int rownum, colsnum; while (option <= endoption) { rownum = here.x + offset[option].x; colsnum = here.y + offset[option].y; if (maze[rownum][colsnum] == 0) break; option++; } if (option <= endoption) { here.x = rownum; here.y = colsnum; pathstack[++stackTop] = here; maze[rownum][colsnum] = 1; option = 0; } else //说明option=4;找不到路了,进行退栈操作; { if (stackTop == -1) return 0; stackTop--; struct position pre= pathstack[stackTop];// if (pre.x == here.x) { option = 2 + pre.y - here.y; } else { option = 3 + pre.x-here.x; } here = pre; } } return 1; } void printfpath() { struct position curpos; while (stackTop != -1) { curpos=pathstack[stackTop]; #pragma message("666") stackTop--; printf("(%d,%d)-->", curpos.x, curpos.y); }printf("n"); } int main() { creatmap(); if(findpath()) { printf("你好!;"); printfpath(); } else { printf("没有找到路径!n"); } system("pause"); return 0; }
#includeusing namespace std; #define ROWS 10 #define COLS 10 template class MyStack { T* pBuff; //内存段首地址 size_t len;//当前存储的数据个数 size_t maxLen;//当前内存段大小 public: MyStack() { pBuff = NULL; len = maxLen =NULL; } ~MyStack() { if (pBuff) delete[]pBuff; pBuff = NULL; len = maxLen = NULL; } void push(const T& data);//入栈 void pop()//删除栈顶元素 { len--; } T getTop() { return pBuff[len - 1]; } bool isEmpty() { return len == 0; } }; template void MyStack ::push(const T& data) { //判断是否需要开内存 if (len >= maxLen) { //1.开内存 //1.1计算新开内存大小 //新的内存段大小是原来的1倍加(原来的二分之一或者1) maxLen = maxLen + (((maxLen >> 1) > 1) ? (maxLen >> 1) : 1); //1.2 开内存。 T* pTem = new T[maxLen]; //2.如果原来的内存段中有数据 if (pBuff) { memcpy(pTem, pBuff, sizeof(T) * len); delete[] pBuff; } //3.pBuff指针指向新开内存段。 pBuff = pTem; } //4.新数据进来。 pBuff[len++] = data; } struct MyPoint { int y; int x; friend bool operator==(const MyPoint& p1, const MyPoint& p2); }; bool operator==(const MyPoint& p1, const MyPoint& p2) { if (p1.x == p2.x && p1.y == p2.y) return true; return false; } enum dirent{p_up,p_left,p_down,p_right }; struct pathNode { int dir;//当前试探方向 bool isFind;//是否走过 0 false 1 true }; int main() { //1.寻路前的准备 //1.1地图 int map[ROWS][COLS] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,1,1,0,1,0,1}, {1,0,1,0,1,1,0,1,0,1}, {1,0,1,0,1,1,0,1,0,1}, {1,0,0,0,1,1,0,0,0,1}, {1,0,1,0,1,1,0,1,1,1}, {1,0,1,0,1,1,0,1,1,1}, {1,0,1,0,1,1,0,1,1,1}, {1,0,1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; //1.2辅助地图(记录当前试探方向,记录有没有走过) pathNode pathMap[ROWS][COLS] = { 0 }; //1.3栈 MyStack stack; //1.4七点 终点 MyPoint begPos = { 1,8 }; MyPoint endPos = { 1,1 }; //标记起点走过 pathMap[begPos.y][begPos.x].isFind = true; stack.push(begPos); //2寻路 MyPoint currentPos = begPos; MyPoint searchPos; bool isFindEnd = false; while (1) { searchPos = currentPos; //重点 //根据当前点的当前试探方向,确定试探点。 switch (pathMap[currentPos.y][currentPos.x].dir) { case p_up: searchPos.y--; pathMap[currentPos.y][currentPos.x].dir++; //2.2判断能不能走 if (pathMap[searchPos.y][searchPos.x].isFind == false//没有走过 && map[searchPos.y][searchPos.x] == 0)//不是障碍 //2.3走 { currentPos = searchPos; //2.4入栈 stack.push(currentPos); //2.5标记走过 pathMap[searchPos.y][searchPos.x].isFind = true; } break; case p_left: searchPos.x--; pathMap[currentPos.y][currentPos.x].dir++; //2.2判断能不能走 if (pathMap[searchPos.y][searchPos.x].isFind == false && map[searchPos.y][searchPos.x] == 0) { currentPos = searchPos; //2.4入栈 stack.push(currentPos); //2.5标记走过 pathMap[searchPos.y][searchPos.x].isFind = true; } break; case p_down: searchPos.y++; pathMap[currentPos.y][currentPos.x].dir++; //2.2判断能不能走 if (pathMap[searchPos.y][searchPos.x].isFind == false && map[searchPos.y][searchPos.x] == 0) //2.3走 { currentPos = searchPos; //2.4入栈 stack.push(currentPos); //2.5标记走过 pathMap[searchPos.y][searchPos.x].isFind = true; } break; case p_right: searchPos.x++; pathMap[currentPos.y][currentPos.x].dir++; //2.2判断能不能走 if (pathMap[searchPos.y][searchPos.x].isFind == false && map[searchPos.y][searchPos.x] == 0) { //2.3走 currentPos = searchPos; //2.4入栈 stack.push(searchPos); //2.5标记走过 pathMap[searchPos.y][searchPos.x].isFind = true; } else //2.6回退 { stack.pop(); currentPos = stack.getTop();//跳到当前栈顶元素。 } break; default:break; } if (currentPos == endPos) { isFindEnd = true; break; } //如果整个地图都没有终点 if (stack.isEmpty()) break; } if(isFindEnd) { cout << "找到终点了!哈哈哈!n"; cout << "path:n"; while (!stack.isEmpty()) { cout<<"("< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)