迷宫问题:
给定一个大小为N*M的迷宫,迷宫由通道和墙壁组成('#','.','S','G'分别表示墙、通道、起点和终点),每一步可以向邻接的上下左右四个方向移动。请给出从起点到终点所需的最小步数。假定起点一定可以到达终点。
没使用STL 我自己模拟队列运行 怎么运行都崩溃
源码
#include<iostream>
#include<queue>
using namespace std;
struct point
{
int x;
int y;
};
char maze[10][11]=
{
"#S######.#",
"......#..#",
".#.##.##.#",
".#........",
"##.##.####",
"....#....#",
".#######.#",
"....#.....",
".####.###.",
"....#...G#"
};
int N=10,M=11;
int sx=0,sy=1;//起点坐标
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int d[10][11];//标记 路径
int bfs()
{
point p,que[100];
int front,rear;
front=rear=0;
que[0].x=sx;
que[0].y=sy;//入队
rear++;
d[sx][sy]=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
d[i][j]=-1;
while(rear!=front)
{
p=que[front];
front++;//出队
if(maze[p.x][p.y]=='G')
{
break;
}
for(int i=0;i<4;i++)
{
point t;
t.x=p.x+dx[i];
t.y=p.y+dy[i];
if(t.x>=0 && t.x<N && t.y>=0 && t.y<M && maze[t.x][t.y]!='#' && d[t.x][t.y] == -1)//表示该点未被访问
{
d[t.x][t.y]=d[p.x][p.y]+1;
que[++rear]=t;
}
}
}
return maze[p.x][p.y];//
}
int main()
{
int res = bfs();
cout<<res<<endl;
return 0;
}