迷宫问题（进阶）CC++

BFS最短路径

利用广度优先搜索来解决迷宫中的最短路径，需要把队列稍微做下调整，博主用的顺序队列，也可以用链式，链式搜索起来方便些。 之前看到有校友用DFS来解决的，但是相对来说算法复杂度要高些，因为DFS一般用来解决所有路径数目问题。 typedef struct{ MazePos data[10000]; int front, rear; int prior[10000]; }SqQueue; 直接甩代码： #include <iostream> #include <malloc.h> using namespace std; typedef struct{ int x, y; }MazePos; char maze[104][104]; int x, y; typedef struct{ MazePos data[10000]; int front, rear; int prior[10000]; }SqQueue; void InitQueue(SqQueue &Q) { Q.front = Q.rear = -1; } bool EmptyQueue(SqQueue &Q) { if(Q.rear == Q.front) return true; else return false; } void EnQueue(SqQueue &Q, MazePos e) { Q.data[++Q.rear] = e; Q.prior[Q.rear] = Q.front; } void DeQueue(SqQueue &Q, MazePos &e) { if(!EmptyQueue(Q)){ e = Q.data[++Q.front]; } } void BFS(SqQueue &Q, MazePos start, MazePos end, int &flag) { MazePos e, k; EnQueue(Q, start); while(!flag && !EmptyQueue(Q)){ DeQueue(Q, e); if((e.x == end.x) && (e.y == end.y)){ flag = 1; return; } if((e.x + 1) < x && (maze[e.x + 1][e.y] != '#')){ k = e; ++k.x; maze[k.x][k.y] = '#'; EnQueue(Q, k); } if((e.y + 1) < y && (maze[e.x][e.y + 1] != '#')){ k = e; ++k.y; maze[k.x][k.y] = '#'; EnQueue(Q, k); } if((e.x - 1) >= 0 && (maze[e.x - 1][e.y] != '#')){ k = e; --k.x; maze[k.x][k.y] = '#'; EnQueue(Q, k); } if((e.y - 1) >= 0 && (maze[e.x][e.y - 1] != '#')){ k = e; --k.y; maze[k.x][k.y] = '#'; EnQueue(Q, k); } } } int main() { int i, j, n, flag, count, prim; SqQueue q; MazePos start, end; cin>>n; while(n--){ InitQueue(q); flag = 0; count = -1; cin>>x>>y; for(i = 0; i < x; i++){ for(j = 0; j < y; j++) cin>>maze[i][j]; } for(i = 0; i < x; i++) for(j = 0; j < y; j++){ if(maze[i][j] == 'S'){ start.x = i; start.y = j; } if(maze[i][j] == 'E'){ end.x = i; end.y = j; } } BFS(q, start, end, flag); if(flag){ prim = q.front; while(q.prior[prim] != -1){ ++count; prim = q.prior[prim]; } cout<<count + 1<<endl; } else cout<<count<<endl; } return 0; }