迷宫问题 （C++代码）

解题思路:迪克斯特拉算法，此题权都为1，故相当于广度优先搜索算法遍历




注意事项:

借助队列进行广度优先搜索遍历

参考代码为了图方便，并未用循环队列，此时应注意容量应该足够大

另外用到了部分C++中的语法





参考代码:

#include<stdio.h>
#include<stdlib.h>
#define INIT_QUEUE_SIZE 10001

typedef struct Node{//定义坐标
 int x;
 int y;
}Node;       

typedef struct Queue{//定义顺序队列
 Node* front;
 Node* rear;
}Queue;

void InitQueue(Queue &Q);
void EnQueue(Queue &Q,Node data);
void DeQueue(Queue &Q);
int EmptyQueue(Queue &Q);
/***************************************************/
int main()
{
 int T,N,M;
 scanf("%d",&T);//n组数据
 while(T--)
 {
  Node start,end;
  int distance=0;//路程 
  int flag=0;
  Node* p=NULL;
  scanf("%d%d",&N,&M);
  getchar(); 
  int Map[N][M],Mark[N][M];//Mark用来标记已经遍历过的点，防止再次遍历
  int next[4][2] = {           //定义四个位移矢量
                    {0,1}, 
                    {1,0},
                    {0,-1},
                    {-1,0}
                    };
      
      
  for(int i=0;i<N;i++)//创建迷宫地图 
  {
   for(int j=0;j<M;j++)
   {
    Map[i][j]=getchar();
    if(Map[i][j]=='S')
     start.x=i,start.y=j;
    if(Map[i][j]=='E')
     end.x=i,end.y=j;
    }
    getchar(); 
    }
    
  Queue Q;
  InitQueue(Q);
  EnQueue(Q,start);
  p=Q.front;
  Mark[start.x][start.y]=1;
  while(!EmptyQueue(Q))
  {
   Node tmp;
   
   for(int i=0;i<4;i++)     //对旁边的四个点进行操作 
    {
     tmp.x=Q.front->x+next[i][0];
     tmp.y=Q.front->y+next[i][1];         
    if(tmp.x<N&&tmp.x>=0)
     if(tmp.y<M&&tmp.y>=0)
      if(Map[tmp.x][tmp.y]!='#'&&Mark[tmp.x][tmp.y]!=1)//检验四个旁边点是否可以通过 
       {
        EnQueue(Q,tmp);
        Mark[tmp.x][tmp.y]=1;
        if(tmp.x==end.x&&tmp.y==end.y) //遍历到终点，算出路程，直接退出 
         {distance=distance+1;
         flag=1;
         
         goto quit;} 
       }
       
    }    if(Q.front==p) //用p标记队列中距离为distance的最后一个结点，当距离distance的结点的相邻点遍历完之后，距离+1，p指向距离为新的distance的最后一个结点
     {
      p=--Q.rear;
      Q.rear++;
      distance++; 
     }
   
    DeQueue(Q);    
  }
  
  quit :
   if(flag==0)//不存在这样的路径
    distance=-1;
   printf("%d\n",distance);
    
  
  } 
  return 0;
 
 }
  
 /**********************************************************/
 void InitQueue(Queue &Q)
 {
  Q.front=Q.rear=(Node*)malloc(sizeof(Node)*INIT_QUEUE_SIZE);
  
  
 }
 void EnQueue(Queue &Q,Node data)
 {
  Q.rear->x=data.x;
  Q.rear->y=data.y;
  Q.rear++;
}
void DeQueue(Queue &Q)
{
 Q.front++;
}
int EmptyQueue(Queue &Q)
{
 if(Q.front==Q.rear)
  return 1;
 return 0;
}