队列求解迷宫最短路径

#include <stdio.h>

typedef struct
{
  int x;
  int y;
  int pre;
}Queue;

Queue Qu[1000];
int Map[20][20];
int front, rear;
int M, N;
int aim[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void Print(int front)
{
  int j, k;
  j = k = front;
  j = front;
  while(j != 0)
  {
    j = Qu[k].pre;
    Qu[k].pre = -1;
    k = j;
  }
  int ns = 0;
  for (int i = 0; i <= front; i++)
  {
    if (Qu[i].pre == -1)
    {
      ns++;
      printf("(%d, %d)", Qu[i].x, Qu[i].y);
      if (ns % 5 == 0)
      {
        printf("\n");
      }
    }
  }
}

void FindPath(int sx, int sy, int ex, int ey)
{
  front = rear = 0;
  Qu[rear].pre = -1;
  int x = Qu[rear].x = sx;
  int y = Qu[rear].y = sy;
  Map[x][y] = 1;
  while(front <= rear)
  {
    if (ex == Qu[front].x && ey == Qu[front].y)
    {
      Print(front);
      return;
    }
    for (int i = 0; i < 4; i++)
    {
      x = Qu[front].x + aim[i][0];
      y = Qu[front].y + aim[i][1];
      if (!Map[x][y])
      {
        rear++;
        Qu[rear].x = x;
        Qu[rear].y = y;
        Qu[rear].pre = front;
        Map[x][y] = 1;
      }
    }
    front++;
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  scanf("%d %d", &M, &N);
  int sx, sy, ex, ey;
  scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
  for (int i = 0; i <= M + 1; i++)
  {
    for (int j = 0; j <= N + 1; j++)
    {
    scanf("%d", &Map[i][j]);
    }
  }
  FindPath(sx, sy, ex, ey);
  return 0;
}

原文地址:https://www.cnblogs.com/lzmfywz/p/3003038.html