数据结构，迷宫。这个该怎么设计？
书上的题，一个走迷宫问题。
我的初步想法是这样的，一个地图结构，一个栈，一个迷宫类。
地图是二维数组，用来表示地图，用1,0表示可过和不可过
栈用来保存路径
迷宫类把地图读进来，匹配路径。
但感觉不好下手。
[解决办法]
1.地图（就是二维数组）
2.路径结点，就是每一个转折点的坐标，由点的结构数组来实现
3.路径，将每个转折点使用直线相连，结构与2相同，用于在地图上绘制路径
[解决办法]
最近刚写了迷宫问题 用了两个算法 一个用递归调用做得 另个一非递归算法做得 还有迷宫无路时 你可以再加一个数组进行标记已经探测的位置
[解决办法]
#include<deque>#include<fstream>#include<iostream>#include<stdlib.h>using namespace std;struct Point{ int x;int y; Point& down(){ x+=1; return *this; } Point& up(){ x-=1; return *this; } Point& left(){ y-=1; return *this; } Point& right(){ y+=1; return *this; }};enum e{RIGHT,DOWN,LEFT,UP};template<int N,int M>struct Map{ int matrix[N][M]; deque<Point> path; void init(istream& i){ for(int x=0;x<N;x++){ for(int y=0;y<M;y++){ i>>matrix[x][y]; } } } bool test(int x,int y){ if(x<0 || x>N-1 || y<0 || y>M-1)return 0; if(matrix[x][y]>=1)return 0; return 1; } bool test(Point p){ return test(p.x,p.y); } bool is_terminal(int x,int y){ if(x==N-1 && y==M-1)return 1; return 0; } bool is_terminal(Point p){ return is_terminal(p.x,p.y); } void set_1(Point p){ matrix[p.x][p.y]=1; } void print(){ deque<Point>::iterator it=path.begin(); while(it!=path.end()){ cout<<"("<<(*it).x<<","<<(*it).y<<")"<<" "; it++; } } void print_(){ for(int x=0;x<N;x++){ for(int y=0;y<M;y++){ cout<<matrix[x][y]<<" "; } cout<<endl; } } void print_path(){ char matri[N][M]; for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ matri[i][j]='#'; } } deque<Point>::iterator it=path.begin(); for(;it!=path.end();it++){ matri[(*it).x][(*it).y]=' '; } for(i=0;i<N;i++){ for(int j=0;j<M;j++){ cout<<matri[i][j]<<" "; } cout<<endl; } } bool is_start(Point p){ return (p.x==0 && p.y==0); } bool isBlocked(Point p){ if(!test(p.x,p.y+1) && !test(p.x,p.y-1) && !test(p.x+1,p.y) && !test(p.x-1,p.y)){ return 1; } return 0; } int search_dir(Point p){ if(test(p.x+1,p.y))return DOWN; if(test(p.x,p.y+1))return RIGHT; if(test(p.x-1,p.y))return UP; if(test(p.x,p.y-1))return LEFT; return -1; } void move(Point& currentPoint){ set_1(currentPoint); path.push_back(currentPoint); if(is_terminal(currentPoint)){ print();cout<<endl; return; } while(isBlocked(currentPoint)){ path.pop_back(); if(path.empty()) {cout<<"no path\n";return;} else { currentPoint=path.back(); } } if(search_dir(currentPoint)==DOWN){ currentPoint.down(); move(currentPoint); } else{ if(search_dir(currentPoint)==RIGHT){ currentPoint.right(); move(currentPoint); } else{ if(search_dir(currentPoint)==UP){ currentPoint.up(); move(currentPoint); } else{ currentPoint.left(); move(currentPoint); } } } } void start(){ fstream f; f.open("E:\\matrix.txt");//此处放迷宫矩阵 init(f); print_(); Point p;p.x=0;p.y=0; move(p); print_path(); f.close(); }};void main(){ Map<9,8> m;//地图大小是9*8 m.start();}
[解决办法]
//存储每一个通道块的相关信息public class PathPoint { //int numCount;// 在路径中的顺序 Point p; int dir; // 表示可以探测的方向 按顺时针共有4个方向 分别表示为 1 2 3 4 public PathPoint(Point p, int dir) { this.p = p; this.dir = dir; } public int getDir() { return dir; } public void setDir(int dir) { this.dir = dir; } public Point getP() { return p; } public void setP(Point p) { this.p = p; }}public class Position { private int row; private int col; public int getCol() { return col; } public Position() { } public Position(int row, int col) { super(); this.row = row; this.col = col; } public void setCol(int col) { this.col = col; } public int getRow() { return row; } public void setRow(int row) { this.row = row; }}public class Maze { public static void main(String args[]) { // 添加墙壁 避免边界判断 int maze[][] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1, 0, 1 }, { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 1, 0, 0, 0, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 }, { 1, 1, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; findPath1(maze); } public static void findPath1(int maze[][]) { Stack s = new Stack(); int size = maze.length - 2; Point p = new Point(1, 1);// 起点 PathPoint now = new PathPoint(p, 1); do { Point next = nextPoint(now); if (next.x == size && next.y == size) { System.out.println(s.size()); while (!s.isEmpty()) { PathPoint path = (PathPoint) s.pop(); System.out.print(path.getP().x + "," + path.getP().y + " "); } return; } else if (maze[next.x][next.y] == 0) { maze[next.x][next.y] = 1; now = new PathPoint(next, 1); s.push(now); } else { if (now.dir == 4) { now = (PathPoint) s.pop(); } else { now.dir++; } } } while (!s.isEmpty()); } public static Point nextPoint(PathPoint pp) { switch (pp.dir) { case 1: return new Point(pp.getP().x, pp.getP().y + 1); case 2: return new Point(pp.getP().x + 1, pp.getP().y); case 3: return new Point(pp.getP().x, pp.getP().y - 1); case 4: return new Point(pp.getP().x - 1, pp.getP().y); } return null; } public static boolean findPath2(int maze[][]) { Stack path = new Stack(); Position[] offset = new Position[4]; int size = maze.length - 2; // 存储移动方向 offset[0] = new Position(0, 1);// right offset[1] = new Position(1, 0); // down offset[2] = new Position(0, -1);// left offset[3] = new Position(-1, 0);// up Position now = new Position(1, 1); maze[1][1] = 1; int option = 0; int lastOption = 3; while (now.getRow() != size || now.getCol() != size) { int r = 0, c = 0;// 表示下一个点的坐标 while (option <= lastOption) { System.out.println(option); r = now.getRow() + offset[option].getRow(); c = now.getCol() + offset[option].getCol(); if (maze[r][c] == 0) break; option++; } if (option <= lastOption) { path.push(now); now = new Position(r, c); maze[r][c] = 1; option = 0; } else { if (path.isEmpty()) return false; Position next = (Position) path.pop(); if (next.getRow() == next.getRow()) { option = 2 + next.getCol() - now.getCol(); } else { option = 3 + next.getRow() - now.getRow(); } now = next; } } return true; }}
[解决办法]
我有代码，我要发吗